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

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.

Series: Combinatorics Seminar

More than 40 years ago, Erdos asked to determine the maximum possible number of edges in a k-uniform hypergraph on n vertices with no matching of size t (i.e., with no t disjoint edges). Although this is one of the most basic problem on hypergraphs, progress on Erdos' question remained elusive. In addition to being important in its own right, this problem has several interesting applications. In this talk we present a solution of Erdos' question for t

Series: Combinatorics Seminar

The correlation of gaps in dimer systems was introduced in 1963 by
Fisher and Stephenson, who looked at the interaction of two monomers
generated by the rigid exclusion of dimers on the closely packed square
lattice. In previous work we considered the analogous problem on the
hexagonal lattice, and we extended the set-up to include the correlation of
any finite number of monomer clusters. For fairly general classes of monomer
clusters we proved that the asymptotics of their correlation is given, for
large separations between the clusters, by a multiplicative version of
Coulomb's law for 2D electrostatics. However, our previous results required
that the monomer clusters consist (with possibly one exception) of an even
number of monomers. In this talk we determine the asymptotics of general
defect clusters along a lattice diagonal in the square lattice (involving an
arbitrary, even or odd number of monomers), and find that it is given by the
same Coulomb law. Of special interest is that one obtains a conceptual
interpretation for the multiplicative constant, as the product of the
correlations of the individual clusters. In addition, we present several
applications of the explicit correlation formulas that we obtain.

Series: Combinatorics Seminar

Erd\H{o}s and Rothschild asked to estimate the maximum number, denotedby $h(n,c)$, such that every $n$-vertex graph with at least $cn^2$edges, each of which is contained in at least one triangle, mustcontain an edge that is in at least $h(n,c)$ triangles. In particular,Erd\H{o}s asked in 1987 to determine whether for every $c>0$ there is$\epsilon>0$ such that $h(n,c)>n^{\epsilon}$ for all sufficientlylarge $n$. We prove that $h(n,c)=n^{O(1/\log \log n)}$ for every fixed$c<1/4$. This gives a negative answer to the question of Erd\H{o}s,and is best possible in terms of the range for $c$, as it is knownthat every $n$-vertex graph with more than $n^2/4$ edges contains anedge that is in at least $n/6$ triangles.Joint work with Jacob Fox.

Series: Combinatorics Seminar

Planar maps are embeddings of connected planar graphs in the plane
considered up to continuous deformation. We will present a ``master
bijection'' for planar maps and show that it can be specialized in
various ways in order to count several families of maps. More
precisely, for each integer d we obtain a bijection between the family
of maps of girth d and a family of decorated plane trees. This gives
new counting results for maps of girth d counted according to the
degree distribution of their faces. Our approach unifies and extends
many known bijections.
This is joint work with Eric Fusy.

Series: Combinatorics Seminar

A famous theorem of Szemeredi and Trotter established a bound on
the maximum number of lines going through k points in the plane. J.
Solymosi conjectured that if one requires the lines to be in general
position -- no two parallel, no three meet at a point -- then one can get a
much tighter bound. Using methods of G. Elekes, we establish Solymosi's
conjecture on the maximum size of a set of rich lines in general position.