BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

István Tomon

István Tomon contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
15works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

15 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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ó.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access