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

Series: Combinatorics Seminar

Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length 2n+1 that have exactly n or n+1 entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit. The middle levels conjecture asserts that this graph has a Hamilton cycle for every n>=1. This conjecture originated probably with Havel, Buck and Wiedemann, but has also been (mis)attributed to Dejter, Erdos, Trotter and various others, and despite considerable efforts it remained open during the last 30 years. In this talk I present a proof of the middle levels conjecture. In fact, I show that the middle layer graph has 2^{2^{\Omega(n)}} different Hamilton cycles, which is best possible. http://www.openproblemgarden.org/op/middle_levels_problem
and http://www.math.uiuc.edu/~west/openp/revolving.html

Series: Combinatorics Seminar

In 2010, Guth and Katz proved that if a collection of N lines in
R^3 contained more than N^{3/2} 2-rich points, then many of these lines must
lie on planes or reguli. I will discuss some generalizations of this result
to space curves in three dimensional vector spaces. This is joint work with
Larry Guth.

Series: Combinatorics Seminar

We look at two combinatorial problems which can be solvedusing careful
estimates for the distribution of smooth numbers. Thefirst is the
Ramsey-theoretic problem to determine the maximal size ofa subset of of
integers containing no 3-term geometric progressions.This problem was
first considered by Rankin, who constructed such asubset with density
about 0.719. By considering progressions among thesmooth numbers, we
demonstrate a method to effectively compute thegreatest possible upper
density of a geometric-progression-free set.Second, we consider the
problem of determining which prime numberoccurs most frequently as the
largest prime divisor on the interval[2,x], as well as the set prime
numbers which ever have this propertyfor some value of x, a problem
closely related to the analysis offactoring algorithms.

Series: Combinatorics Seminar

A fourientation of a graph is a choice for each edge of whether
to orient it in either direction, bidirect it, or leave it unoriented. I
will present joint work with Sam Hopkins where we describe classes of
fourientations defined by properties of cuts and cycles whose cardinalities
are given by generalized Tutte polynomial evaluations of the form:
(k+l)^{n-1}(k+m)^g T (\frac{\alpha k + \beta l +m}{k+l},
\frac{\gamma k +l + \delta m}{k+m}) for \alpha,\gamma \in {0,1,2} and
\beta, \delta \in {0,1}. We also investigate classes of 4-edge
colorings defined via generalized notions of internal and external
activity, and we show that their enumerations agree with those of the
fourientation classes. We put forth the problem of finding a bijection
between fourientations and 4-edge-colorings which respects all of the given
classes. Our work unifies and extends earlier results for fourientations
due to myself, Gessel and Sagan, and Hopkins and Perkinson, as well as
classical results for full orientations due to Stanley, Las Vergnas, Greene
and Zaslavsky, Gioan, Bernardi and others.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

Series: Combinatorics Seminar

When studying the mixing of random walks on groups, information about the relative likelihoods of the elements under the walk can serve to help understand the mixing and reveal some internal structure. Starting with some elementary arguments of Diaconis and Isaacs and moving into arguments using representation theory of the symmetric group, I'll demonstrate some total and partial orders on finite groups that describe the relative likeliness under random walks. No prior knowledge is assumed.

Series: Combinatorics Seminar

In this talk we will survey some recent development on statistical properties of matchings of very large and infinite graphs. The main goal of the talk is to describe a few applications of a new concept called matching measure. These applications include new results on the number of (perfect) matchings in large girth graphs as well as simple new proofs of certain statistical physical theorems. In particular, we will sketch the proof of Friedland's Lower Matching Conjecture, and a new proof of Schrijver's and Gurvits's theorems. This talk is based on joint papers with various subsets of Miklos Abert, Peter E. Frenkel, Tamas Hubai and Gabor Kun.

Series: Combinatorics Seminar

Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. We consider natural local moves on some realizations of the Catalan sequence and derive estimates of the mixing time of the corresponding Markov chains. We present a new O(n^2 log n) bound on the mixing time for the random transposition chain on Dyck paths, and raise several open problems, including the optimality of the above bound. (Joint work with Prasad Tetali and Damir Yelliusizov.)

Series: Combinatorics Seminar

Let B(d,n) denote the d-regular graph on n vertices which consists of the disjoint union of complete bipartite graphs. It follows from the results of Kahn and of Zhao that among all d-regular graphs on n vertices B(d,n) maximizes the number of independent sets. In this talk, we show a spectral stability phenomenon of this result in the following sense. The eigenvalues of (the adjacency matrix) of B(d,n) are known to be d, -d and zeroes and we show that, if the smallest eigenvalue of G is bounded away from -d, then the number of independent sets in G is exponentially smaller than that of B(d,n). Furthermore, we extend this method to study the well-known hard-core model from statistical physics. Given a d-regular bipartite graph G whose second smallest eigenvalue is bounded away from -d. Let Ind(G) denote the set of all independent sets of G. Among others, we show that in this case the random independent set I\in Ind(G), drawn from the hard-core distribution with activation parameter lambda>> (log d)/d, is essentially completely (up to o(|I|) vertices) contained in one of the partition classes of G. (This is joint work with Prasad Tetali.)