Some of my most notable papers
String graphs have the Erdős-Hajnal property. JEMS (combinatorial geometry, Ramsey theory)
The following Ramsey type problem naturally appears in combinatorial geometry. Given a collection of n geometric objects on the plane, how large of a subcollection can one find in which any two elements are intersecting, or any two elements are disjoint. Perhaps the most general instance of this problem is when the geometric objects are curves, or equivalently, arc-wise connected sets. Confirming a conjecture of Alon, Pach, Pinchasi, Radoičić and Sharir, we show that the answer is polynomial in n. Our main technical lemma led to further breakthroughs on the Erdős-Hajnal conjecure.
Lower bounds for piercing and coloring boxes. Advances in Math. (combinatorial geometry, Ramsey theory)
Configurations of axis parallel boxes are extensively studied, yet there are still many mysteries sorruounding them. It was proved by Gyárfás and Lehel in 1985 that if a family of boxes in dimension d does not contain k pairwise disjoint elements, then there exists a number f_d(k), only depending on d and k, such that all the boxes can be pierced by f_d(k) points. It was a longstanding problem (the planar case already considered in the 60's) whether f_d(k) grows linearly in k in any fixed dimension. We not only show that this is false for d>2, we provide the lower bound k(log k)^(d-2-o(1)), which is tight up to the o(1) term.
The extremal number of tight cycles. (joint work with B. Sudakov) IMRN (extremal hypergraph theory)
A tight cycle in an r-uniform hypergraph is a sequence of vertices such that any r consecutive forms an edge in the cyclic order. This is a natural extension of the usual notion of a graph cycle to hypergraphs. It was an old question of Sós to determine the maximum number of edges of an r-uniform hypergraph on n vertices containing no tight cycle. By adapting the theory of sublinear expanders to hypergraphs, we essentially resolve this problem by proving the bound n^(r-1+o(1)), which is optimal up to the (necessary) o(1) term.
The extremal number of surfaces. (joint work with A. Kupavskii, A. Polyanskii, and D. Zakharov) IMRN (extremal hypergraph theory)
An old result of Brown, Erdős, and Sós states that if a 3-uniform hypergraph on n vertices contains no triangulation of the sphere, then it has at most O(n^5/2) edges, and this bound is the best possible. Linial conjectured that the same bound holds if we forbid a triangulation of the torus instead of the sphere. We prove this conjecture, and its extension for all closed orientable surfaces.
Exponential Erdős-Szekeres theorem for matrices. (joint work with R. A. Çiçeksiz , Z. Jin, E. Räty) (Ramsey theory)
In 1993, Fishburn and Graham proved that there exists a smallest number N=N(n) such that any N-by-N integer matrix contains an n-by-n submatrix, in which each row and column is monotone. It is not difficult to show that N(n) is at most double exponential in n. We improve this bound to exponential in n^(4+o(1)), almost matching the lower bound n^(n/2).
Dedekind's problem in the hypergrid. (joint work with V. Falgas-Ravry and E. Räty) (poset theory)
One of the oldest problems in combinatorics is Dedekind's problem from 1897, which asks for the number of antichains in the Boolean lattice 2^[n]. While this problem was essentially solved by Kleitman and Markowsky in the 70's, its natural extension about counting antichains in [t]^n (where the ordering is the natural coordinate-wise ordering) gained a lot of attention recently due to its connection to other enumerative, and also hypergraph Ramsey problems. We essentially resolve this problem up to lower order terms.
Small doubling, atomic structure and ℓ-divisible set families. (joint work with L. Gishboliner, B. Sudakov) Discrete Analysis (extremal set theory)
The celebrated Eventown theorem states that if any two sets in a family on n elements has an intersection of even size, then the family contains at most 2^(n/2) sets. If ℓ is an integer, one can consider the generalization of this theorem, where the intersection of any two elements is divisible by ℓ. A natural conjecture to make is that the maximum size of such a family is 2^(n/ℓ), but this was disproved by Frankl and Odlyzko in 1983, who showed that the right answer is 2^(n log ℓ/ℓ). They conjectured that, however, if one replaces pairwise intersections with k-wise intersections for some k=k(ℓ), the maximum size is indeed 2^(n/ℓ). We prove this conjecture in a strong sense by establishing a linear algebraic small-doubling type result.
Hasse diagrams with large chromatic number. (joint work with A. Suk) Bulletin of LMS (poset and Ramsey theory, combinatorial geometry)
The chromatic number of Hasse diagrams is studied since the 60's. As Hasse diagrams are triangle-free, there is no obvious way to force large chromatic number. However, as many results show, the chromatic number can be arbitrarily large even for posets with very special properties. On the other hand, no construction of n vertex Hasse diagram was known with chromatic number more than logarithmic. We present a simple construction of a Hasse diagram with n vertices and chromatic number of the order n^(1/4). This also give a disjointness graph of n curves that is triangle-free and have the same chromatic number, beating he previous logarithmic lower bound.
The poset on connected graphs is Sperner. (joint work with S. G. Z. Smith) JCTA (poset theory)
Katona proposed the following beautiful problem in Sperner theory. Consider the poset, whose elements are the connected graphs on a vertex set X, and the ordering is given by the subgraph relation. Is it true the largest antichain in this poset is a level, i.e. a set of connected graphs with given number of edges? We prove that the answer is yes.
On a conjecture of Füredi. European J. of Comb. (poset theory)
An old conjecture of Füredi asks whether the Boolean lattice 2^[n] can be partitioned into the minimum number of chains such that any two chains have essentially the same size (their sizes differ by at most 1). We prove that there is a partition where every chain has the same size up to a constant factor. In particular, we prove a much more general theorem, which shows that a similar statement holds for any poset that is regular in some sense (has the normalized matching property). Such chain decompositions found applications in partitioning and extremal problems as well.