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

Series: Combinatorics Seminar

Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is at least the expected number of homomorphisms from $H$ to the binomial random graph with the same expected edge density as $G$. In this talk, I will present two approaches to the conjecture. First, I will introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure, and show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$. Second, I will prove that if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then the Cartesian product of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture. Joint work w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford).

Series: Combinatorics Seminar

The number of permutations with specified descent set is maximized on the (classical) alternating permutations, which are counted by the Euler numbers. Asymptotics for the Euler numbers are well-studied. A counterpart of the descent statistic is the exceedance set statistic which is known to be maximized on a single run of consecutive exceedances. An exact enumeration is known, but the asymptotics have not been studied. We provide asymptotics using multivariate analytic combinatorics (providing a uniformity that goes beyond the range of a basic central limit theorem). This answers a question of E. Clark and R. Ehrenborg. As further applications we also discuss generalized pattern avoidance, and the number of orbit types (n-cycles) that admit a stretching pair (a certificate for "turbulence" in the context of combinatorial dynamics). This includes joint work with R. Ferraz de Andrade and B. Nagle and J. N. Cooper.

Series: Combinatorics Seminar

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties:
- its edge expansion is at least c/log n;
- its diameter is O(log n);
- its vertex expansion is at least c/log n;
- it has a linearly long path;
- its mixing time is O(log^2n)
All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).

Series: Combinatorics Seminar

An equitable two-coloring for a hypergraph is a proper vertex coloring such that the cardinalities of color classes differ by at most one. The well-known Hajnal-Szemerédi theorem states that any graph G with maximum vertex degree d admits an equitable coloring with d + 1 colors. In our talk we shall discuss a similar question for uniform hypergraphs and present a new bound in a Hajnal-Szemerédi-type theorem for some classes of uniform hypergraphs. The proof is based on the random recoloring method and the results of Lu and Székely concerning negative correlations in the space of random bijections.

Series: Combinatorics Seminar

The problem of extending results in extremal combinatorics to sparse random and pseudorandom structures has attracted the attention of many researchers in the last decades. The breakthroughs due to several groups in the last few years have led to a better understanding of the subject, however, many questions remain unsolved. After a short introduction into this field we shall focus on some results in extremal (hyper)graph theory and additive combinatorics. Along the way some open problems will be given.

Series: Combinatorics Seminar

An open problem of interest in combinatorial number theory is that of providing a non-ergodic proof to the so called polynomial Szemeredi theorem. So far, the landmark result in this venue is that of Green who considered the emergence of 3-term arithmetic progressions whose gap is a sum of two squares (not both zero) in dense sets of integers. In view of this we consider the following problem. Given two dense subsets A and S of a finite abelian group G, what is the weakest "pseudorandomness assumption" once put on S implies that A contains a 3-term arithmetic progressions whose gap is in S? We answer this question for G=Z_n and G = F_p^n. To quantify pseudorandomness we use Gowers norms.

Series: Combinatorics Seminar

The Erdos-Szekeres (happy ending) theorem claims that among any N points in general position in the plane there are at least log_4(n) of them that are the vertices of a convex polygon. I will explain generalizations of this result that were discovered in the last 30 years involving pseudoline arrangements and families of convex bodies. After surveying some previous work I will present the following results:
1) We improve the upper bound of the analogue Ramsey function for families of disjoint and noncrossing convex bodies. In fact this follows as a corollary of the equivalence between a conjecture of Goodman and Pollack about psudoline arrangements and a conjecture of Bisztrinsky and Fejes Toth about families of disjoint convex bodies. I will say a few words about how we show this equivalence.
2) We confirm a conjecture of Pach and Toth that generalizes the previous result. More precisely we give suffcient and necesary conditions for the existence of the analogue Ramsey function in the more general case in which each pair of bodies share less than k common tangents (for every fixed k).
These results are joint work with Andreas Holmsen and Michael Dobbins.

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.