Source author record

István Tomon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

18works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Robust (rainbow) subdivisions and simplicial cycles

We present several results in extremal graph and hypergraph theory of topological nature. First, we show that if $α>0$ and $\ell=Ω(\frac{1}α\log\frac{1}α)$ is an odd integer, then every graph $G$ with $n$ vertices and at least $n^{1+α}$ edges contains an $\ell$ -subdivision of the complete graph $K_t$ , where $t=n^{Θ(α)}$ . Also, this remains true if in addition the edges of $G$ are properly colored, and one wants to find a rainbow copy of such a subdivision. In the sparser regime, we show that properly edge colored graphs on $n$ vertices with average degree $(\log n)^{2+o(1)}$ contain rainbow cycles, while average degree $(\log n)^{6+o(1)}$ guarantees rainbow subdivisions of $K_t$ for any fixed $t$ , thus improving recent results of Janzer and Jiang et al., respectively. Furthermore, we consider certain topological notions of cycles in pure simplicial complexes (uniform hypergraphs). We show that if $G$ is a $2$ -dimensional pure simplicial complex ( $3$ -graph) with $n$ $1$ -dimensional and at least $n^{1+α}$ 2-dimensional faces, then $G$ contains a triangulation of the cylinder and the Möbius strip with $O(\frac{1}α\log\frac{1}α)$ vertices. We present generalizations of this for higher dimensional pure simplicial complexes as well. In order to prove these results, we consider certain (properly edge colored) graphs and hypergraphs $G$ with strong expansion. We argue that if one randomly samples the vertices (and colors) of $G$ with not too small probability, then many pairs of vertices are connected by a short path whose vertices (and colors) are from the sampled set, with high probability.

preprint2022arXiv

Evasive sets, covering by subspaces, and point-hyperplane incidences

Given positive integers $k\leq d$ and a finite field $\mathbb{F}$ , a set $S\subset\mathbb{F}^{d}$ is $(k,c)$ -subspace evasive if every $k$ -dimensional affine subspace contains at most $c$ elements of $S$ . By a simple averaging argument, the maximum size of a $(k,c)$ -subspace evasive set is at most $c |\mathbb{F}|^{d-k}$ . When $k$ and $d$ are fixed, and $c$ is sufficiently large, the matching lower bound $Ω(|\mathbb{F}|^{d-k})$ is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of $(k,c)$ -evasive sets in case $d$ is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of $k$ -dimensional linear hyperplanes needed to cover the grid $[n]^{d}\subset \mathbb{R}^{d}$ is $Ω_{d}\big(n^{\frac{d(d-k)}{d-1}}\big)$ , which matches the upper bound proved by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in $\mathbb{R}^{d}$ assuming their incidence graph avoids the complete bipartite graph $K_{c,c}$ for some large constant $c=c(d)$ .

preprint2022arXiv

On $3$ -graphs with no four vertices spanning exactly two edges

Let $D_2$ denote the $3$ -uniform hypergraph with $4$ vertices and $2$ edges. Answering a question of Alon and Shapira, we prove an induced removal lemma for $D_2$ having polynomial bounds. We also prove an Erdős-Hajnal-type result: every induced $D_2$ -free hypergraph on $n$ vertices contains a clique or an independent set of size $n^{c}$ for some absolute constant $c > 0$ . In the case of both problems, $D_2$ is the only nontrivial $k$ -uniform hypergraph with $k\geq 3$ which admits a polynomial bound.

preprint2022arXiv

Regular subgraphs of linear hypergraphs

We prove that the maximum number of edges in a 3-uniform linear hypergraph on $n$ vertices containing no 2-regular subhypergraph is $n^{1+o(1)}$ . This resolves a conjecture of Dellamonica, Haxell, Luczak, Mubayi, Nagle, Person, Rödl, Schacht and Verstraëte. We use this result to show that the maximum number of edges in a $3$ -uniform hypergraph on $n$ vertices containing no immersion of a closed surface is $n^{2+o(1)}$ . Furthermore, we present results on the maximum number of edges in $k$ -uniform linear hypergraphs containing no $r$ -regular subhypergraph.

preprint2022arXiv

Small subgraphs with large average degree

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$ , we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also optimal up to the constant hidden in the $O(.)$ notation, and resolves a conjecture of Verstraëte.

preprint2022arXiv

The Turán number of the grid

For a positive integer $t$ , let $F_t$ denote the graph of the $t\times t$ grid. Motivated by a 50-year-old conjecture of Erdős about Turán numbers of $r$ -degenerate graphs, we prove that there exists a constant $C=C(t)$ such that $\mathrm{ex}(n,F_t)\leq Cn^{3/2}$ . This bound is tight up to the value of $C$ . One of the interesting ingredients of our proof is a novel way of using the tensor power trick.

preprint2021arXiv

Flattening rank and its combinatorial applications

Given a $d$ -dimensional tensor $T:A_1\times\dots\times A_d\rightarrow \mathbb{F}$ (where $\mathbb{F}$ is a field), the $i$ -flattening rank of $T$ is the rank of the matrix whose rows are indexed by $A_{i}$ , columns are indexed by $B_{i}=A_1\times\dots\times A_{i-1}\times A_{i+1}\times\dots\times A_{d}$ and whose entries are given by the corresponding values of $T$ . The max-flattening rank of $T$ is defined as $\text{mfrank}(T)=\max_{i\in [d]}\text{frank}_{i}(T)$ . A tensor $T:A^{d}\rightarrow\mathbb{F}$ is called semi-diagonal, if $T(a,\dots,a)\neq 0$ for every $a\in A$ , and $T(a_{1},\dots,a_{d})=0$ for every $a_{1},\dots,a_{d}\in A$ that are all distinct. In this paper we prove that if $T:A^{d}\rightarrow\mathbb{F}$ is semi-diagonal, then $\text{mfrank}(T)\geq \frac{|A|}{d-1}$ , and this bound is the best possible. We give several applications of this result, including a generalization of the celebrated Frankl-Wilson theorem on forbidden intersections. Also, addressing a conjecture of Aharoni and Berger, we show that if the edges of an $r$ -uniform multi-hypergraph $\mathcal{H}$ are colored with $z$ colors such that each colorclass is a matching of size $t$ , then $\mathcal{H}$ contains a rainbow matching of size $t$ provided $z>(t-1)\binom{rt}{r}$ . This improves previous results of Alon and Glebov, Sudakov and Szabó.

preprint2021arXiv

Long directed paths in Eulerian digraphs

An old conjecture of Bollobás and Scott asserts that every Eulerian directed graph with average degree $d$ contains a directed cycle of length at least $Ω(d)$ . The best known lower bound for this problem is $Ω(d^{1/2})$ by Huang, Ma, Shapira, Sudakov and Yuster. They asked whether this estimate can be improved at least for directed paths instead of cycles and whether one can find a long path starting from any vertex if the host digraph is connected. In this paper we break the $\sqrt{d}$ barrier, showing how to find a path of length $Ω(d^{1/2+1/40})$ from any vertex of a connected Eulerian digraph.

preprint2021arXiv

Ramsey properties of semilinear graphs

A graph $G$ is semilinear of complexity $t$ if the vertices of $G$ are elements of $\mathbb{R}^{d}$ for some $d\in\mathbb{Z}^{+}$ , and the edges of $G$ are defined by the sign patterns of $t$ linear functions $f_1,\dots,f_t:\mathbb{R}^{d}\times \mathbb{R}^{d}\rightarrow\mathbb{R}$ . We show that semilinear graphs of constant complexity have very tame Ramsey properties. More precisely, we prove that if $G$ is a semilinear graph of complexity $t$ which contains no clique of size $s$ and no independent set of size $n$ , then $G$ has at most $O_{s,t}(n)\cdot(\log n)^{O_t(1)}$ vertices. We also show that the logarithmic term cannot be omitted. In particular, this implies that if $G$ is a semilinear graph of constant complexity on $n$ vertices, and $G$ contains no clique of size $s$ , then $G$ can be properly colored with $\mbox{polylog}(n)$ colors. In the past 60 years, this coloring question was extensively studied for several special instances of semilinear graphs, e.g. shift graphs, intersection and disjointness graphs of certain geometric objects, and overlap graphs. Our main result provides a general upper bound on the chromatic number of all such, seemingly unrelated, graphs. Furthermore, we consider the symmetric Ramsey problem for semilinear graphs as well. It is known that if there exists an intersection graph of $N$ boxes in $\mathbb{R}^{d}$ (such graphs are semilinear of complexity $2d$ ) that contains no clique or independent set of size $n$ , then $N=O_d(n^2(\log n)^{d-1})$ . That is, the exponent of $n$ does not grow with the dimension. We prove a result about the symmetric Ramsey properties of semilinear graphs, which puts this phenomenon in a more general context.

preprint2020arXiv

Erdős-Hajnal-type results for ordered paths

An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer $k$ , there exists a constant $c_k>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement contains an induced monotone path of size $k$ , has either a clique or an independent set of size at least $n^{c_k}$ . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs. A key idea of the above paper was to show that any unordered graph on $n$ vertices that does not contain an induced path of size $k$ , and whose maximum degree is at most $c(k)n$ for some small $c(k)>0$ , contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for $k\geq 3$ , by a construction of Fox. We provide further examples how this statement fails for ordered graphs avoiding other ordered trees as well.

preprint2020arXiv

Hasse diagrams with large chromatic number

For every positive integer $n$ , we construct a Hasse diagram with $n$ vertices and chromatic number $Ω(n^{1/4})$ , which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number $Θ(\log n)$ . In addition, if we also require that our Hasse diagram has girth at least $k\geq 5$ , we can achieve a chromatic number of at least $n^{\frac{1}{2k-3}+o(1)}$ . These results have the following surprising geometric consequence. They imply the existence of a family $\mathcal{C}$ of $n$ curves in the plane such that the disjointness graph $G$ of $\mathcal{C}$ is triangle-free (or have high girth), but the chromatic number of $G$ is polynomial in $n$ . Again, the previously known best construction, due to Pach, Tardos and Tóth, had only logarithmic chromatic number.

preprint2020arXiv

Infinite Sperner's theorem

One of the most classical results in extremal set theory is Sperner's theorem, which says that the largest antichain in the Boolean lattice $2^{[n]}$ has size $Θ\big(\frac{2^n}{\sqrt{n}}\big)$ . Motivated by an old problem of Erdős on the growth of infinite Sidon sequences, in this note we study the growth rate of maximum infinite antichains. Using the well known Kraft's inequality for prefix codes, it is not difficult to show that infinite antichains should be "thinner" than the corresponding finite ones. More precisely, if $\mathcal{F}\subset 2^{\mathbb{N}}$ is an antichain, then $\liminf_{n\rightarrow \infty}\big|\mathcal{F} \cap 2^{[n]}\big|\left(\frac{2^n}{n\log n}\right)^{-1}=0.$ Our main result shows that this bound is essentially tight, that is, we construct an antichain $\mathcal{F}$ such that $\liminf_{n\rightarrow \infty}\big|\mathcal{F} \cap 2^{[n]}\big|\left(\frac{2^n}{n\log^{C} n}\right)^{-1}>0$ holds for some absolute constant $C>0$ .

preprint2020arXiv

String graphs have the Erdős-Hajnal property

A string graph is the intersection graph of curves in the plane. We prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^{c}$ .

preprint2020arXiv

The extremal number of tight cycles

A tight cycle in an $r$ -uniform hypergraph $\mathcal{H}$ is a sequence of $\ell\geq r+1$ vertices $x_1,\dots,x_{\ell}$ such that all $r$ -tuples $\{x_{i},x_{i+1},\dots,x_{i+r-1}\}$ (with subscripts modulo $\ell$ ) are edges of $\mathcal{H}$ . An old problem of V. Sós, also posed independently by J. Verstraëte, asks for the maximum number of edges in an $r$ -uniform hypergraph on $n$ vertices which has no tight cycle. Although this is a very basic question, until recently, no good upper bounds were known for this problem for $r\geq 3$ . Here we prove that the answer is at most $n^{r-1+o(1)}$ , which is tight up to the $o(1)$ error term. Our proof is based on finding robust expanders in the line graph of $\mathcal{H}$ together with certain density increment type arguments.

preprint2020arXiv

Turán-type results for intersection graphs of boxes

In this short note, we prove the following analog of the Kővári-Sós-Turán theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in $\mathbb{R}^{d}$ such that $G$ contains no copy of $K_{t,t}$ , then $G$ has at most $ctn(\log n)^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$ . Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit et al. of $K_{2,2}$ -free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

preprint2016arXiv

Almost tiling of the Boolean lattice with copies of a poset

Let $P$ be a partially ordered set. If the Boolean lattice $(2^{[n]},\subset)$ can be partitioned into copies of $P$ for some positive integer $n$ , then $P$ must satisfy the following two trivial conditions: (1) the size of $P$ is a power of $2$ , (2) $P$ has a unique maximal and minimal element. Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well. In this paper, we show that if $P$ only satisfies condition (2), we can still almost partition $2^{[n]}$ into copies of $P$ . We prove that if $P$ has a unique maximal and minimal element, then there exists a constant $c=c(P)$ such that all but at most $c$ elements of $2^{[n]}$ can be covered by disjoint copies of $P$ .

preprint2016arXiv

Partitioning the Boolean lattice into copies of a poset

Let $P$ be a poset of size $2^k$ that has a greatest and a least element. We prove that, for sufficiently large $n$ , the Boolean lattice $2^{[n]}$ can be partitioned into copies of $P$ . This resolves a conjecture of Lonc.

preprint2016arXiv

The multiplication table problem for bipartite graphs

We investigate the following generalisation of the 'multiplication table problem' of Erdős: given a bipartite graph with $m$ edges, how large is the set of sizes of its induced subgraphs? Erdős's problem of estimating the number of distinct products $ab$ with $a,b \le n$ is precisely the problem under consideration when the graph in question is the complete bipartite graph $K_{n,n}$ . In this note, we prove that the set of sizes of the induced subgraphs of any bipartite graph with $m$ edges contains $Ω(m/(\log m)^{12})$ distinct elements.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

István Tomon

Research overview

Is this your work?

18 publications

Robust (rainbow) subdivisions and simplicial cycles

Evasive sets, covering by subspaces, and point-hyperplane incidences

On $3$ -graphs with no four vertices spanning exactly two edges

Regular subgraphs of linear hypergraphs

Small subgraphs with large average degree

The Turán number of the grid

Flattening rank and its combinatorial applications

Long directed paths in Eulerian digraphs

Ramsey properties of semilinear graphs

Erdős-Hajnal-type results for ordered paths

Hasse diagrams with large chromatic number

Infinite Sperner's theorem

String graphs have the Erdős-Hajnal property

The extremal number of tight cycles

Turán-type results for intersection graphs of boxes

Almost tiling of the Boolean lattice with copies of a poset

Partitioning the Boolean lattice into copies of a poset

The multiplication table problem for bipartite graphs

See the researcher in context

Building this map preview

István Tomon

Research overview

Is this your work?

18 publications

Robust (rainbow) subdivisions and simplicial cycles

Evasive sets, covering by subspaces, and point-hyperplane incidences

On 333-graphs with no four vertices spanning exactly two edges

Regular subgraphs of linear hypergraphs

Small subgraphs with large average degree

The Turán number of the grid

Flattening rank and its combinatorial applications

Long directed paths in Eulerian digraphs

Ramsey properties of semilinear graphs

Erdős-Hajnal-type results for ordered paths

Hasse diagrams with large chromatic number

Infinite Sperner's theorem

String graphs have the Erdős-Hajnal property

The extremal number of tight cycles

Turán-type results for intersection graphs of boxes

Almost tiling of the Boolean lattice with copies of a poset

Partitioning the Boolean lattice into copies of a poset

The multiplication table problem for bipartite graphs

See the researcher in context

Building this map preview

On $3$ -graphs with no four vertices spanning exactly two edges