Highlights

  • String graphs have the Erdős-Hajnal property (2020) arXiv:2002.10350

The following Ramsey type question is extensively studied in combinatorial and computational geometry. Given a collection of $n$ geometric objects in the plane (e.g. disks, rectangles, convex sets), how large of a subcollection can we find in which any two objects are disjoint, or any two are intersecting. We prove that in the case of curves, the answer is $n^c$, where $c>0$ is a constant. This shows the the answer to the aforementioned question is always at least n^c for any 'reasonable' collection of geometric objects on the plane, and confirms a conjecture of Alon, Pach, Pinchasi, Radoicic and Sharir, also reiterated by Fox and Pach. Moreover, the main lemma developed for the resolution of this problem played a key role in the celebrated solution of the Erdős-Hajnal conjecture for the 5-cycle by Chudnovsky, Scott, Seymour and Spirkl.

  • The extremal number of tight cycles (with B. Sudakov), Int. Math. Res. Not. (2021), doi.org/10.1093/imrn/rnaa396

A tight cycle in an $r$-uniform hypergraph $H$ is a sequence of $\ell\geq r+1$ vertices $x_1,...,x_l$ such that all consecutive $r$-tuples in the cyclic order are edges of $H$. How many edges can an $r$-uniform hypergraph $H$ on $n$ vertices have if it contains no tight cycles? This natural question is an easy exercise if $r=2$, but turned out to be particularly difficult for $r\geq 3$. We prove that the answer is $n^{r-1+o(1)}$, which is the best possible up to the (necessary) $o(1)$-term, thus settling an old problem of Sós, also reiterated by Verstraete.

  • Small doubling, atomic structure and ℓ-divisible set families (with L. Gishboliner, B. Sudakov) (2021) arXiv:2103.16479

If $\mathcal{F}\subset 2^{[n]}$ is a family such that the intesection of any number of sets in $\mathcal{F}$ is divisible by $\ell$, then it is not difficult to show that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$. The famous Eventown theorem of Berkelamp (1969) and Graver (1975) states that if $\ell=2$ it is enough to consider pairwise intersections to get the same conclusion. This is no longer true for larger $\ell$, but in 1983, Frankl and Odlyzko conjectured that there exists some $k=k(\ell)$ such that if any $k$ distinct elements of $\mathcal{F}$ has size divisible by $\ell$, then $|\mathcal{F}|\leq 2^{(1+o(1))n/\ell}$. We completely resolve this old conjecture in a strong sense by showing that such $\mathcal{F}$ satisfies $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}+O(1)$, and the $O(1)$ term is not needed if (and only if) $\ell$ divides $n$. Our proof relies on a novel 'small doubling' type argument on set systems.

  • The poset on connected graphs is Sperner (with S.G.Z. Smith), Journal of Combinatorial Theory, Series A 150 (2017): 162-181.

Sperner's theorem about the size of maximal antichains in the Boolean lattice is one of the cornerstone results of extremal combinatorics. Katona asked the following beautiful extension of this theorem. Consider the family of connected graphs on a given vertex set, and order them by the subgraph relation. Is it true the maximal antichain in this poset is a 'level', that is, a family of graphs having the same number of edges? We answer this question in the affirmative.

  • The extremal number of surfaces (with A. Kupavskii, A. Polyanskii, D. Zakharov) (2020), to appear in Int. Math. Res. Not., arXiv:2010.07191

A well known result of Brown, Erdős and Sós from 1973 states that if a 3-uniform hypergraph on $n$ vertices does not contain a triangulation of the sphere, then it has $O(n^{5/2})$ edges, and this bound is the best possible. We show that the same bound holds if we forbid triangulations of the torus, or any fixed orientable surface, thus confirming a conjecture of Linial.

  • On the size of $k$-cross-free families (with A. Kupavskii, J. Pach), Combinatorica 39 (1) (2019): 153-164.

Two subsets $A$ and $B$ of a groundset $X$ are crossing if they are in general position, that is, $A\cap B, A\setminus B, B\setminus A, X\setminus (A\cup B)$ are all nonempty. A family of subsets of $X$ is $k$-cross-free if it contains no $k$ pairwise crossing sets. In 1979, Karzanov and Lomonosov observed that 3-cross-free families arise in connection to multicommodity-flow problems, and proposed the conjecture that the maximum size of a $k$-cross-free family on $n$ elements is $O_k(n)$. This conjecture received considerable attention, as $k$-cross-free families also naturally appear in combinatorial geometry and in the study of phylogenetic trees. However, in general the best known bound was the easy to prove $O_k(n\log n)$. Making the first significant progress in this more than 40 years old problem, we show the bound $O_k(n\log^* n)$.

  • The Turán number of bipartite graphs with no $K_{t,t}$ (with B. Sudakov), Proceedings of the American Mathematical Society 148 (7) (2020): 2811-2818.

One of the most well known results in extremal graph theory is the following theorem of Füredi (1991) and Alon, Krivelevich and Sudakov (2003). If $H$ is a bipartite graph such that every degree in one of the vertex classes is at most $t$, then any graph $G$ on $n$ vertices avoiding $H$ has $O(n^{2-1/t})$ edges, and this bound is the best possible. We show that this can be improved to $o(n^{2-1/t})$ if (and only if, assuming some well known conjecture holds) $H$ contains no complete bipartite graph with vertex classes of size $t$. This confirmed a conjecture of Conlon, Janzer and Lee.

List of publications

Submitted papers

  • Small doubling, atomic structure and ℓ-divisible set families (with L. Gishboliner, B. Sudakov) (2021) arXiv:2103.16479

  • Ramsey properties of algebraic graphs and hypergraphs (with B. Sudakov) (2021) arXiv:2103.05618

  • Ramsey properties of semilinear graphs (2021) arXiv:2102.12464

  • Long directed paths in Eulerian digraphs (with O. Janzer, B. Sudakov) (2021) arXiv:2101.11601

  • Infinite Sperner's theorem (with B. Sudakov, A. Zs. Wagner) (2020) arXiv:2008.04804

  • String graphs have the Erdős-Hajnal property (2020) arXiv:2002.10350

  • Bipartite Turán problems for ordered graphs (with A. Methuku) (2019) arXiv:1908.03189

  • Flattening rank and its combinatorial applications (with D. Correia, B. Sudakov) (2021), to appear in Linear Algebra and its Applications, arXiv:2103.03217

  • Erdős-Hajnal-type results for ordered paths (with J. Pach) (2020), accepted by Journal of Combinatorial Theory, Series B, arXiv:2004.04594

  • Turán type results for intersection graphs of boxes (with D. Zakharov) (2020), to appear in Combinatorics, Probability and Computing, arXiv:2009.04380

  • Uniform chain decompositions and applications (with B. Sudakov, A. Zs. Wagner) (2019), to appear in Random Structures & Algorithms, arXiv:1911.09533

  • The extremal number of surfaces (with A. Kupavskii, A. Polyanskii, D. Zakharov) (2020), to appear in Int. Math. Res. Not., arXiv:2010.07191

Journal publications

  • A sharp threshold phenomenon in string graphs, Discrete Comput. Geom. (2021),doi.org/10.1007/s00454-021-00279-3

  • The extremal number of tight cycles (with B. Sudakov), Int. Math. Res. Not. (2021), doi.org/10.1093/imrn/rnaa396

  • Hasse diagrams with large chromatic number (with A. Suk), Bulletin of London Math. Society (2020), doi.org/10.1112/blms.12457

  • Large homogeneous submatrices (with D. Korándi, J. Pach), SIAM J. Discrete Math. 34 (4) (2020): 2532-2552.

  • Colorings with only rainbow arithmetic progressions (with J. Pach), Acta Mathematica Hungarica 161 (2) (2020): 507-515.

  • The Turán number of bipartite graphs with no $K_{t,t}$ (with B. Sudakov), Proceedings of the American Mathematical Society 148 (7) (2020): 2811-2818.

  • On the chromatic number of disjointness graphs of curves (with J. Pach), Journal of Combinatorial Theory, Series B 144 (2020): 167-190.

  • Improved Ramsey-type results in comparability graphs (with D. Korándi), Combinatorics, Probability and Computing 29 (5) (2020): 747-756.

  • Packing the Boolean lattice with copies of a poset, Journal of London Mathematical Society 101 (2) (2020): 589-611.

  • Ordered graphs and large bi-cliques in intersection graphs of curves (with J. Pach), European Journal of Combinatorics 82 (2019): 102994.

  • Forbidden induced subposets of given height, Journal of Combinatorial Theory, Series A 161 (2019): 537-562.

  • On the Turán number of ordered forests (with D. Korándi, G. Tardos, C. Weidert), Journal of Combinatorial Theory, Series A 165 (2019): 32-43.

  • Partitioning the Boolean lattice into copies of a poset (with V. Gruslys, I. Leader), Journal of Combinatorial Theory, Series A 161 (2019): 81-98.

  • On the size of $k$-cross-free families (with A. Kupavskii, J. Pach), Combinatorica 39 (1) (2019): 153-164.

  • Ramsey graphs induce subgraphs with many different sizes (with B. P. Narayanan, J. Sahasrabudhe) Combinatorica (39) (2019): 215-237.

  • On the Turán number of some ordered even cycles (with E. Győri, D. Korándi, A. Methuku, C. Tompkins, M. Vizér), European Journal of Combinatorics 73 (2018): 81-88.

  • Almost Tiling of the Boolean Lattice with Copies of a Poset, Electronic Journal of Combinatorics 25 (1) (2018): P1.38.

  • Induced subgraphs with many distinct degrees (with B. P. Narayanan), Combinatorics, Probability and Computing 27 (1) (2018): 110-123.

  • The poset on connected graphs is Sperner (with S.G.Z. Smith), Journal of Combinatorial Theory, Series A 150 (2017): 162-181.

  • The multiplication table problem for bipartite graphs (with B. P. Narayanan, J. Sahasrabudhe), Combinatorica 37 (5) (2017): 991-1010.

  • Turán-type results for complete $h$-partite graphs in comparability and incomparability graphs, Order 33 (3) (2016): 537-556.

  • Decompositions of the Boolean lattice into rank-symmetric chains, The Electronic Journal of Combinatorics 23 (2) (2016): P2.53.

  • Improved bounds on the partitioning of the Boolean lattice into chains of equal size, Discrete Mathematics 339 (1) (2016): 333-343.

  • On a conjecture of Füredi, European Journal of Combinatorics 49 (2015): 1-12.

  • On the chromatic number of regular graphs of matrix algebras, Linear Algebra and its Applications 475 (2015): 154-162.

  • On the number of occurrences of the $k$-th smallest distance between points in convex position, Discrete Mathematics 338 (6) (2015): 990-993.

  • Point sets with every triangle having a large angle, Moscow Journal of Combinatorics an Number Theory 4 (3) (2014): 40-68.

Some conference papers

  • Coloring Hasse Diagrams and Disjointness Graphs of Curves (with J. Pach), in: International Symposium on Graph Drawing and Network Visualization (2019): 244-250. Springer, Cham

  • On the chromatic number of disjointness graphs of curves (with J. Pach), in:35th International Symposium on Computational Geometry, SoCG 2019,129Leibniz Zentrum, Dagstuhl (2019): 54:1-54:17.