- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles? In general this decision problem is undecidable for infinite regions and NP-complete for finite regions. In the case of simply connected finite regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. We construct a fixed set of rectangular tiles whose tileability problem is NP-complete even for simply connected regions.This is joint work with Igor Pak.

Series: Combinatorics Seminar

A hereditary chip-firing model is a chip-firing game whose dynamics
are induced by an abstract simplicial complex \Delta on the vertices
of a graph, where \Delta may be interpreted as encoding graph gluing
data. These models generalize two classical chip-firing games: The
Abelian sandpile model, where \Delta is disjoint collection of
points, and the cluster firing model, where \Delta is a single
simplex. Two fundamental properties of these classical models extend
to arbitrary hereditary chip-firing models: stabilization is
independent of firings chosen (the Abelian property) and each
chip-firing equivalence class contains a unique recurrent
configuration. We will present an explicit bijection between the
recurrent configurations of a hereditary chip-firing model on a graph
G and the spanning trees of G and, if time permits, we will discuss
chip-firing via gluing in the context of binomial ideals and metric
graphs.

Series: Combinatorics Seminar

Over the past 40 years, researchers have made many connections between the dimension of posets and the issue of planarity for graphs and diagrams, but there appears to be little work connecting dimension to structural graph theory. This situation has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael Joret, made the following striking conjecture, which has now been turned into a theorem: The dimension of a poset is bounded in terms of its height and the tree-width of its cover graph. In this talk, I will outline how Joret was led to this conjecture by the string of results on planarity. I will also sketch how the resolution of his conjecture points to a number of new problems, which should interest researchers in both communities.

Series: Combinatorics Seminar

Associated to every finite graph G there is a canonical ideal
which encodes the linear equivalences of divisors on G. We study this ideal
and its associated initial ideal. We give an explicit description of their
syzygy modules and the Betti numbers in terms of the "connected flags" of G.
This resolves open questions posed by Postnikov-Shapiro,
Perkinson-Perlmen-Wilmes, and Manjunath-Sturmfels.
No prior knowledge in advanced commutative algebra will be assumed. This is
a joint work with Fatemeh Mohammadi.

Series: Combinatorics Seminar

We will discuss some problems related to coloring the edges or vertices of a random graph. In particular we will discuss results on (i) the game chromatic number; (ii) existence of rainbow Hamilton cycles; (iii) rainbow connection. (** Please come a few minutes earlier for a pizza lunch **)

Series: Combinatorics Seminar

We introduce a general Minimum Linear Ordering Problem (MLOP): Given a nonnegative set function f on a finite set V, find a linear ordering on V such that the sum of the function values for all the suffixes is minimized. This problem generalizes well-known problems such as the Minimum Linear Arrangement, Min Sum Set Cover, and Multiple Intents Ranking. Extending a result of Feige, Lovasz, and Tetali (2004) on Min Sum Set Cover, we show that the greedy algorithm provides a factor 4 approximate optimal solution when the cost function f is supermodular. We also present a factor 2 rounding algorithm for MLOP with a monotone submodular cost function, while the non monotone case remains wide open. This is joint work with Satoru Iwata and Pushkar Tripathi.

Series: Combinatorics Seminar

We study an Achlioptas-process version of the random k-SAT process: a
bounded number of k-CNF clauses are drawn uniformly at random at each step,
and exactly one added to the growing formula according to a particular
rule. We prove the existence of a rule that shifts the satisfiability
threshold. This extends a well-studied area of probabilistic combinatorics
and random graphs to random CSP's. In particular, while a rule to delay
the 2-SAT threshold was known previously, this is the first proof of a rule
to shift the threshold of a CSP that is NP-hard. We then propose a gap
decision problem based upon this semi-random model with the aim of
investigating the hardness of the random k-SAT decision problem.

Series: Combinatorics Seminar

In this talk, we consider a well-known combinatorial search problem.
Suppose that there are n identical looking coins and some of them are
counterfeit.
The weights of all authentic coins are the same and known a priori.
The weights of counterfeit coins vary but different from the weight of
an authentic coin.
Without loss of generality, we may assume the weight of authentic coins is
0.
The problem is to find all counterfeit coins by weighing (queries) sets of
coins
on a spring scale. Finding the optimal number of queries is difficult even
when there are only 2 counterfeit coins.
We introduce a polynomial time randomized algorithm to find all
counterfeit coins when the number of them is known to be at most
m \geq 2 and the weight w(c) of each counterfeit coin c satisfies
\alpha \leq |w(c)| \leq \beta
for fixed constants \alpha, \beta > 0. The query complexity of the
algorithm is O(\frac{m \log n }{\log m}), which is optimal up to a
constant factor. The algorithm uses, in part, random walks.
The algorithm may be generalized to find all edges of a hidden
weighted graph using a similar type of queries. This graph finding
algorithm
has various applications including DNA sequencing.

Series: Combinatorics Seminar

Sarkozy's problem is a classical problem in additive number
theory, which asks for the size of the largest subset A of
{1,2,...,n} such that the difference set A-A does not contain
a (non-zero) square. I will discuss the history of this problem, some
recent progress that I and several collaborators have
made on it, and our future research plans.

Series: Combinatorics Seminar

Let H_k(n,s) be a k-uniform hypergraphs on n vertices in which the largest
matching has s edges. In 1965 Erdos conjectured that the
maximum number of edges in H_k(n,s) is attained
either when H_k(n,s) is a clique of size ks+k-1, or
when the set of edges of H_k(n,s) consists of all k-element
sets which intersect some given set S of s elements.
In the talk we prove this conjecture
for k = 3 and n large enough.
This is a joint work with Katarzyna Mieczkowska.