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

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.

Series: Combinatorics Seminar

A small set expander is a graph where every set of sufficiently small
size has near perfect edge expansion. This talk concerns the computational
problem of distinguishing a small set-expander, from a graph containing a
small non-expanding set of vertices. This problem henceforth referred to
as the Small-Set Expansion problem has proven to be intimately connected to
the complexity of large classes of combinatorial optimization problems.
More precisely, the small set expansion problem can be shown to be
directly related to the well-known Unique Games Conjecture -- a
conjecture that has numerous implications in approximation algorithms.
In this talk, we motivate the problem, and survey recent work consisting of
algorithms and interesting connections within graph expansion, and its
relation to Unique Games Conjecture.

Series: Combinatorics Seminar

Wiring diagrams are classical objects of combinatorics. Plabic graphs were
defined by Postnikov, to study the total positivity of the Grassmannian. We
will show how to generalize several definitions and properties of wiring
diagrams to Plabic graphs, proving a conjecture by Leclerc-Zelevinsky and
Scott on the way. We will begin with a brief introduction to total
positivity and end with connection to cluster algebras. Major part of the
talk comes from a joint work with Alexander Postnikov and David Speyer.

Series: Combinatorics Seminar

The quotient of a Boolean algebra by a cyclic group is proven to have a symmetric chain decomposition. This generalizes earlier work of Griggs, Killian and Savage on the case of prime order, giving an explicit construction for any order, prime or composite. The combinatorial map specifying how to proceed downward in a symmetric chain is shown to be a natural cyclic analogue of Kashiwara's sl_2 lowering operator in the theory of crystal bases. The talk will include a survey of related past work on symmetric chain decomposition and unimodality by Greene-Kleitman, Griggs-Killian-Savage, Proctor, Stanley and others as well as a discussion of open questions that still remain. This is joint work with Anne Schilling.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

Say that a graph with maximum degree at most $d$ is {\it $d$-bounded}. For$d>k$, we prove a sharp sparseness condition for decomposition into $k$ forestsand a $d$-bounded graph. The condition holds for every graph with fractionalarboricity at most $k+\FR d{k+d+1}$. For $k=1$, it also implies that everygraph with maximum average degree less than $2+\FR{2d}{d+2}$ decomposes intoone forest and a $d$-bounded graph, which contains several earlier results onplanar graphs.

Series: Combinatorics Seminar

Immersion is a containment relation between graphs (or digraphs) which is
defined similarly to the more familiar notion of minors, but is incomparable
to it. Of particular interest is to find conditions on a graph (or digraph)
G which guarantee that G contains a clique (or bidirected clique) of order t
as an immersion. This talk will begin with a gentle introduction, and will
then share two new results of this form, one for graphs and one for
digraphs. In the former case, we find that minimum degree 200t is
sufficient, and in the later case, we find that minimum degree t(t-1) is
sufficient, provided that G is Eulerian. These results come from joint work
with Matt DeVos, Jacob Fox, Zdenek Dvorak, Bojan Mohar and Diego Scheide.