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

Series: Combinatorics Seminar

Graphons are limit objects that are associated with convergent sequences of
graphs. Problems from extremal combinatorics and theoretical computer science
led to a study of graphons determined by finitely many subgraph densities,
which are referred to as finitely forcible graphons. In 2011, Lovasz and
Szegedy asked several questions about the complexity of the topological space
of so-called typical vertices of a finitely forcible graphon can be. In
particular, they conjectured that the space is always compact. We disprove the
conjecture by constructing a finitely forcible graphon such that the associated
space of typical vertices is not compact. In fact, our construction actually
provides an example of a finitely forcible graphon with the space which is even
not locally compact. This is joint work with Roman Glebov and Dan Kral.

Series: Combinatorics Seminar

A well-known problem in geometry, which may be traced back to the Renaissance artist Albrecht Durer, is concerned with cutting a convex polyhedral surface along some spanning tree of its edges so that it may be isometrically embedded, or developed without overlaps, into the plane. We show that this is always possible after an affine transformation of the surface. In particular, unfoldability of a convex polyhedron does not depend on its combinatorial structure, which settles a problem of Croft, Falconer, and Guy. Among other techniques, the proof employs a topological characterization for embeddings among immersed planar disks.

Series: Combinatorics Seminar

We study the Maker-Breaker component game, played on the edge set of a
regular graph.
Given a graph G, the s-component (1:b) game is defined as follows: in
every round Maker claims one free edge of G and Breaker claims b free
edges.
Maker wins this game if her graph contains a connected component of
size at least s; otherwise, Breaker wins the game.
For all values of Breaker's bias b, we determine whether Breaker wins
(on any d-regular graph) or Maker wins (on almost every d-regular
graph) and provide explicit winning strategies for both players.
To this end, we prove an extension of a theorem by
Gallai-Hasse-Roy-Vitaver about graph orientations without long
directed simple paths.
Joint work with Alon Naor.

Series: Combinatorics Seminar

Studying the ferromagnetic Ising model with zero applied field reduces
to sampling even
subgraphs X of G with probability proportional to
\lambda^{|E(X)|}. In this paper we present a class of Markov chains
for sampling even subgraphs, which contains the classical
single-site dynamics M_G and generalizes it to nonlocal
chains. The idea is based on the fact that even subgraphs form a
vector space over F_2
generated by a cycle basis of G. Given any cycle basis C of a
graph G, we define a Markov chain M(C) whose transitions are
defined by symmetric difference with an element of C.
We characterize cycle bases into two types: long and short.
We show that for any long cycle basis C of any graph G, M(C)
requires exponential time to mix when \lambda is small.
All fundamental cycle bases of the grid in 2 and 3 dimensions
are of this type. Moreover, on the 2-dimensional grid, short bases
appear to behave like M_G. In particular, if G has
periodic boundary conditions, all short bases yield Markov chains that
require exponential time to mix for small enough \lambda. This is
joint work with Isabel Beichl, Noah Streib, and Francis Sullivan.

Series: Combinatorics Seminar

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties. [Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.]

Series: Combinatorics Seminar

I will survey the major results in graph and hypergraph Ramsey theory and present some recent results on hypergraph Ramsey numbers. This includes a hypergraph generalization of the graph Ramsey number R(3,t) proved recently with Kostochka and Verstraete. If time permits some proofs will be presented.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

Let A be a multiplicative subgroup of Z_p^*. Define the k-fold
sumset of A to be kA={x_1+...+x_k:x_1,...,x_k in A}. Recently, Shkredov
has shown that |2A| >> |A|^(8/5-\epsilon) for |A| < p^(9/17). In this talk we
will discuss extending this result to hold for |A| < p^(5/9). In addition,
we will show that 6A contains Z_p^* for |A| > p^(33/71 +\epsilon).

Series: Combinatorics Seminar

For two graphs, G and F, we write G\longrightarrow F if every
2-coloring of the edges of G results in a monochromatic copy of F.
A graph G is k-Folkman if G\longrightarrow K_k and G\not\supset K_{k+1}. We
show that there is a constant c > 0 such that for every k \ge 2 there exists a
k-Folkman graph on at most 2^{k^{ck^2}} vertices. Our probabilistic proof is
based on a careful analysis of the growth of constants in a modified proof of the
result by Rodl and the speaker from 1995 establishing a threshold for the Ramsey
property of a binomial random graph G(n,p).
Thus, at the same time, we provide a new proof of that result (for two colors) which
avoids the use of regularity lemma.
This is joint work with Vojta Rodl and Mathias Schacht.

Series: Combinatorics Seminar

For a given finite graph G of minimum degree at least k, let
G_{p} be a random subgraph of G obtained by taking each edge
independently with probability p. We prove that (i) if p \ge
\omega/k for a function \omega=\omega(k) that tends to infinity
as k does, then G_p asymptotically almost surely contains a
cycle (and thus a path) of length at least (1-o(1))k, and (ii) if
p \ge (1+o(1))\ln k/k, then G_p asymptotically almost surely
contains a path of length at least k. Our theorems extend
classical results on paths and cycles in the binomial random graph,
obtained by taking G to be the complete graph on k+1 vertices.
Joint w/ Michael Krivelevich (Tel Aviv), Benny Sudakov (UCLA).