István Tomon - Highlights

From small eigenvalues to large cuts, and Chowla’s cosine problem. (with Z. Jin, A. Milojevic, and S. Zhang) (harmonic analysis, spectral graph theory)

We study structural properties of graphs whose smallest eigenvalue is small in absolute value. As an application, we prove the first polynomial bound for Chowla's cosine problem from 1965 about the minimum of cosine polynomials. As a second application, we prove a weak version of a celebrated conjecture of Alon, Bollobás, Krivelevich and Sudakov on the maximum cut of graphs containing no cliques of given size.

https://arxiv.org/pdf/2509.03490

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 in 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 conjecture.

https://doi.org/10.4171/JEMS/1362

Lower bounds for piercing and coloring boxes. Adv. 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 show that this is false for d>2 by proving f_d(k)>k(log k)^(d-2-o(1)), which is also tight up to the o(1) term. We also settle the Ramsey problem about intersection graphs of boxes up to double-logarithmic factors.

https://doi.org/10.1016/j.aim.2023.109360

Positive discrepancy, MaxCut, and eigenvalues of graphs. (with E Räty and B. Sudakov) Trans. AMS (spectral graph theory)

A celebrated result of Alon from 1993 gives sharp bounds on the minimum bisection of n-vertex d-regular graphs, as long as d<n^1/9. With the introduction of novel linear algebraic techniques, we extend this result up to d<(1/2-eps)n, and uncover the highly unexpected behavior that the extremal function goes through at least three phase transitions. This also leads to an extension of the Alon-Boppana theorem for dense graphs, showing a similarly strange behavior.

https://arxiv.org/pdf/2311.02070.pdf

The extremal number of tight cycles. (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 in 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.

https://doi.org/10.1093/imrn/rnaa396

The extremal number of surfaces. (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 natural extension for every closed orientable surface.

https://doi.org/10.1093/imrn/rnab099

Exponential Erdős-Szekeres theorem for matrices. (with R. A. Çiçeksiz , Z. Jin, and E. Räty) Proc. LMS (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 to N(n)<exp(n^(4+o(1))), getting close to the best known lower bound N(n)>n^(n/2).

https://arxiv.org/pdf/2305.07003.pdf

Dedekind's problem in the hypergrid. (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.

https://arxiv.org/pdf/2310.12946.pdf

Matrix discrepancy and the log-rank conjecture. (with B. Sudakov) Mathematical Programming (linear algebra)

We prove a sharp bound on the discrepancy of low rank Boolean matrices, and use it to make progress on the celebrated Log-rank conjecture of Lovász and Saks.

https://doi.org/10.1007/s10107-024-02117-9

Small doubling, atomic structure and ℓ-divisible set families. (with L. Gishboliner and B. Sudakov) Discrete Analysis (extremal set theory)

The celebrated Eventown theorem states that if the intersection of any two sets in a family on n elements is even, 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 sets 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 close to 2^(n/ℓ). We prove this conjecture in a strong sense by establishing a linear algebraic small-doubling type result.

https://doi.org/10.19086/da.38586

Hasse diagrams with large chromatic number. (with A. Suk) Bull. LMS (poset 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 in n. We present a simple construction of a Hasse diagram with n vertices and chromatic number of the order n^(1/4). This also shows the existence of a disjointness graph of n curves that is triangle-free and have the same chromatic number, beating he previous logarithmic lower bound.

https://doi.org/10.1112/blms.12457

The poset on connected graphs is Sperner. (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.

https://doi.org/10.1016/j.jcta.2017.03.003

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.

https://doi.org/10.1016/j.ejc.2015.02.026