BZPEER

preprint2022arXiv

Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

In this paper, we consider a randomized greedy algorithm for independent sets in $r$ -uniform $d$ -regular hypergraphs $G$ on $n$ vertices with girth $g$ . By analyzing the expected size of the independent sets generated by this algorithm, we show that $α(G)\geq (f(d,r)-ε(g,d,r))n$ , where $ε(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$ , and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

preprint2022arXiv

Set-coloring Ramsey numbers via codes

For positive integers $n,r,s$ with $r > s$ , the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$ . The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$ , while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

preprint2020arXiv

A generalization of the Bollobás set pairs inequality

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $n \geq k \geq t \geq 2$ , we consider a collection of $k$ families $\mathcal{A}_i: 1 \leq i \leq k$ where $\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$ so that $A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \emptyset$ if and only if there are at least $t$ distinct indices $i_1,i_2,\dots,i_k$ . Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $β_{k,t}(n)$ of the families with ground set $[n]$ .

preprint2020arXiv

Triangle-free Subgraphs of Hypergraphs

In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$ . We prove that if $H$ is an $n$ -vertex $r$ -uniform hypergraph with maximum degree $\triangle$ , then as $\triangle \rightarrow \infty$ , the number of edges in a densest $T$ -free subhypergraph of $H$ is at least $\frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.$ For $r = 3$ , this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$ -vertex triple system with edge-probability $p$ such that $pn^3\rightarrow\infty$ as $n\rightarrow\infty$ , then with high probability as $n \rightarrow \infty$ , the number of edges in a densest $T$ -free subhypergraph is $\min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.$ We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.

preprint2016arXiv

The extremal function for cycles of length $\ell$ mod $k$

Burr and Erdős conjectured that for each $k,\ell \in \mathbb Z^+$ such that $k \mathbb Z + \ell$ contains even integers, there exists $c_k(\ell)$ such that any graph of average degree at least $c_k(\ell)$ contains a cycle of length $\ell$ mod $k$ . This conjecture was proved by Bollobás, and many successive improvements of upper bounds on $c_k(\ell)$ appear in the literature. In this short note, for $1 \leq \ell \leq k$ , we show that $c_k(\ell)$ is proportional to the largest average degree of a $C_{\ell}$ -free graph on $k$ vertices, which determines $c_k(\ell)$ up to an absolute constant. In particular, using known results on Turán numbers for even cycles, we obtain $c_k(\ell) = O(\ell k^{2/\ell})$ for all even $\ell$ , which is tight for $\ell \in \{4,6,10\}$ . Since the complete bipartite graph $K_{\ell - 1,n - \ell + 1}$ has no cycle of length $2\ell$ mod $k$ , it also shows $c_k(\ell) = Θ(\ell)$ for $\ell = Ω(\log k)$ .

preprint2015arXiv

A survey of Turán problems for expansions

The $r$ -expansion $G^+$ of a graph $G$ is the $r$ -uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a vertex subset of size $r-2$ disjoint from $V(G)$ such that distinct edges are enlarged by disjoint subsets. Let $ex_r(n,F)$ denote the maximum number of edges in an $r$ -uniform hypergraph with $n$ vertices not containing any copy of the $r$ -uniform hypergraph $F$ . Many problems in extremal set theory ask for the determination of $ex_r(n,G^+)$ for various graphs $G$ . We survey these Turán-type problems, focusing on recent developments.

preprint2015arXiv

The number of trees in a graph

Let $T$ be a tree with $t$ edges. We show that the number of isomorphic (labeled) copies of $T$ in a graph $G = (V,E)$ of minimum degree at least $t$ is at least $2|E| \prod_{v \in V} (d(v) - t + 1)^{\frac{(t-1)d(v)}{2|E|}}.$ Consequently, any $n$ -vertex graph of average degree $d$ and minimum degree at least $t$ contains at least $nd(d-t+1)^{t-1}$ isomorphic (labeled) copies of $T$ . This answers a question of Dellamonica et. al. (where the above statement was proved when $T$ is the path with three edges) while extending an old result of Erd\H os and Simonovits.

preprint2014arXiv

Cycles in triangle-free graphs of large chromatic number

More than twenty years ago Erdős conjectured~\cite{E1} that a triangle-free graph $G$ of chromatic number $k \geq k_0(\varepsilon)$ contains cycles of at least $k^{2 - \varepsilon}$ different lengths as $k \rightarrow \infty$ . In this paper, we prove the stronger fact that every triangle-free graph $G$ of chromatic number $k \geq k_0(\varepsilon)$ contains cycles of $(\frac{1}{64} - \varepsilon)k^2 \log k$ consecutive lengths, and a cycle of length at least $(\tfrac{1}{4} - \varepsilon)k^2 \log k$ . As there exist triangle-free graphs of chromatic number $k$ with at most roughly $4k^2 \log k$ vertices for large $k$ , theses results are tight up to a constant factor. We also give new lower bounds on the circumference and the number of different cycle lengths for $k$ -chromatic graphs in other monotone classes, in particular, for $K_r$ -free graphs and graphs without odd cycles $C_{2s+1}$ .

preprint2014arXiv

On Coupon Colorings of Graphs

Let $G$ be a graph with no isolated vertices. A {\em $k$ -coupon coloring} of $G$ is an assignment of colors from $[k] := \{1,2,\dots,k\}$ to the vertices of $G$ such that the neighborhood of every vertex of $G$ contains vertices of all colors from $[k]$ . The maximum $k$ for which a $k$ -coupon coloring exists is called the {\em coupon coloring number} of $G$ , and is denoted $χ_{c}(G)$ . In this paper, we prove that every $d$ -regular graph $G$ has $χ_{c}(G) \geq (1 - o(1))d/\log d$ as $d \rightarrow \infty$ , and the proportion of $d$ -regular graphs $G$ for which $χ_c(G) \leq (1 + o(1))d/\log d$ tends to $1$ as $|V(G)| \rightarrow \infty$ .

preprint2014arXiv

On sets of integers with restrictions on their products

A {\em product-injective labeling} of a graph $G$ is an injection $χ: V(G) \to \mathbb{Z}$ such that $χ(u)χ(v) \not= χ(x)χ(y)$ for any distinct edges $uv, xy\in E(G)$ . Let $P(G)$ be the smallest $N \geq 1$ such that there exists a product-injective labeling $χ: V(G) \rightarrow [N]$ . Let $P(n,d)$ be the maximum possible value of $P(G)$ over $n$ -vertex graphs $G$ of maximum degree at most $d$ . In this paper, we determine the asymptotic value of $P(n,d)$ for all but a small range of values of $d$ relative to $n$ . Specifically, we show that there exist constants $a,b > 0$ such that $P(n,d) \sim n$ if $d \leq \sqrt{n}(\log n)^{-a}$ and $P(n,d) \sim n\log n$ if $d \geq \sqrt{n}(\log n)^{b}$ .

preprint2014arXiv

Turan Problems and Shadows II: Trees

The expansion $G^+$ of a graph $G$ is the 3-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let ex $_r(n,F)$ denote the maximum number of edges in an $r$ -uniform hypergraph with $n$ vertices not containing any copy of $F$ . The authors \cite{KMV} recently determined ex $_3(n,G^+)$ more generally, namely when $G$ is a path or cycle, thus settling conjectures of Füredi-Jiang \cite{FJ} (for cycles) and Füredi-Jiang-Seiver \cite{FJS} (for paths). Here we continue this project by determining the asymptotics for ex $_3(n,G^+)$ when $G$ is any fixed forest. This settles a conjecture of Füredi \cite{Furedi}. Using our methods, we also show that for any graph $G$ , either ex $_3(n,G^{+}) \leq \left(\frac{1}{2} + o(1)\right)n^2$ or ex $_3(n,G^{+}) \geq (1 + o(1))n^2,$ thereby exhibiting a jump for the Turán number of expansions.

preprint2014arXiv

Turan Problems and Shadows III: expansions of graphs

The expansion $G^+$ of a graph $G$ is the $3$ -uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a new vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let $ex_3(n,F)$ denote the maximum number of edges in a $3$ -uniform hypergraph with $n$ vertices not containing any copy of a $3$ -uniform hypergraph $F$ . The study of $ex_3(n,G^+)$ includes some well-researched problems, including the case that $F$ consists of $k$ disjoint edges, $G$ is a triangle, $G$ is a path or cycle, and $G$ is a tree. In this paper we initiate a broader study of the behavior of $ex_3(n,G^+)$ . Specifically, we show $ex_3(n,K_{s,t}^+) = Θ(n^{3 - 3/s})$ whenever $t > (s - 1)!$ and $s \geq 3$ . One of the main open problems is to determine for which graphs $G$ the quantity $ex_3(n,G^+)$ is quadratic in $n$ . We show that this occurs when $G$ is any bipartite graph with Turán number $o(n^φ)$ where $φ= \frac{1 + \sqrt{5}}{2}$ , and in particular, this shows $ex_3(n,Q^+) = Θ(n^2)$ where $Q$ is the three-dimensional cube graph.

preprint2013arXiv

A counterexample to sparse removal

The Turán number of a graph $H$ , denoted $\mbox{ex}(n,H)$, is the maximum number of edges in an $n$ -vertex graph with no subgraph isomorphic to $H$ . Solymosi conjectured that if $H$ is any graph and $\mbox{ex}(n,H) = O(n^α)$ where $α> 1$ , then any $n$ -vertex graph with the property that each edge lies in exactly one copy of $H$ has $o(n^α)$ edges. This can be viewed as conjecturing a possible extension of the removal lemma to sparse graphs, and is well-known to be true when $H$ is a non-bipartite graph, in particular when $H$ is a triangle, due to Ruzsa and Szemerédi. Using Sidon sets we exhibit infinitely many bipartite graphs $H$ for which the conjecture is false.

preprint2013arXiv

Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

Given positive integers $n$ and $d$ , let $M(n,d)$ denote the maximum size of a permutation code of length $n$ and minimum Hamming distance $d$ . The Gilbert-Varshamov bound asserts that $M(n,d) \geq n!/V(n,d-1)$ where $V(n,d)$ is the volume of a Hamming sphere of radius $d$ in $§_n$ . Recently, Gao, Yang, and Ge showed that this bound can be improved by a factor $Ω(\log n)$ , when $d$ is fixed and $n \to \infty$ . Herein, we consider the situation where the ratio $d/n$ is fixed and improve the Gilbert-Varshamov bound by a factor that is \emph{linear in $n$ }. That is, we show that if $d/n < 0.5$ , then $M(n,d)\geq cn\,\frac{n!}{V(n,d-1)}$ where $c$ is a positive constant that depends only on $d/n$ . To establish this result, we follow the method of Jiang and Vardy. Namely, we recast the problem of bounding $M(n,d)$ into a graph-theoretic framework and prove that the resulting graph is locally sparse.

preprint2013arXiv

Small maximal partial ovoids in generalized quadrangles

A {\em maximal partial ovoid} of a generalized quadrangle is a maximal set of points no two of which are collinear. The problem of determining the smallest size of a maximal partial ovoid in quadrangles has been extensively studied in the literature. In general, theoretical lower bounds on the size of a maximal partial ovoid in a quadrangle of order $(s,t)$ are linear in $s$ . In this paper, in a wide class of quadrangles of order $(s,t)$ we give a construction of a maximal partial ovoid of size at most $s \cdot \mbox{polylog}(s)$, which is within a polylogarithmic factor of theoretical lower bounds. The construction substantially improves previous quadratic upper bounds in quadrangles of order $(s,s^2)$ , in particular in the well-studied case of the elliptic quadrics $Q^-(5,s)$ .

preprint2012arXiv

Turan numbers for bipartite graphs plus an odd cycle

For an odd integer $k$ , let $\mathcal{C}_k = \{C_3,C_5,...,C_k\}$ denote the family of all odd cycles of length at most $k$ and let $\mathcal{C}$ denote the family of all odd cycles. Erdős and Simonovits \cite{ESi1} conjectured that for every family $\mathcal{F}$ of bipartite graphs, there exists $k$ such that $\ex{n}{\mathcal{F} \cup \mathcal{C}_k} \sim \ex{n}{\mathcal{F} \cup \mathcal{C}}$ as $n \rightarrow \infty$ . This conjecture was proved by Erdős and Simonovits when $\mathcal{F} = \{C_4\}$ , and for certain families of even cycles in \cite{KSV}. In this paper, we give a general approach to the conjecture using Scott's sparse regularity lemma. Our approach proves the conjecture for complete bipartite graphs $K_{2,t}$ and $K_{3,3}$ : we obtain more strongly that for any odd $k \geq 5$ , \[ \ex{n}{\mathcal{F} \cup \{C_k\}} \sim \ex{n}{\mathcal{F} \cup \mathcal{C}}\] and we show further that the extremal graphs can be made bipartite by deleting very few edges. In contrast, this formula does not extend to triangles -- the case $k = 3$ -- and we give an algebraic construction for odd $t \geq 3$ of $K_{2,t}$ -free $C_3$ -free graphs with substantially more edges than an extremal $K_{2,t}$ -free bipartite graph on $n$ vertices. Our general approach to the Erdős-Simonovits conjecture is effective based on some reasonable assumptions on the maximum number of edges in an $m$ by $n$ bipartite $\mathcal{F}$ -free graph.

preprint2011arXiv

On a conjecture of Erdos and Simonovits: Even Cycles

Let $\mc{F}$ be a family of graphs. A graph is {\em $\mc{F}$-free} if it contains no copy of a graph in $\mc{F}$ as a subgraph. A cornerstone of extremal graph theory is the study of the {\em Turán number} $ex(n,\mc{F})$, the maximum number of edges in an $\mc{F}$-free graph on $n$ vertices. Define the {\em Zarankiewicz number} $z(n,\mc{F})$ to be the maximum number of edges in an $\mc{F}$-free {\em bipartite} graph on $n$ vertices. Let $C_k$ denote a cycle of length $k$ , and let $\mc{C}_k$ denote the set of cycles $C_{\ell}$ , where $3 \le \ell \leq k$ and $\ell$ and $k$ have the same parity. Erdős and Simonovits conjectured that for any family $\mc{F}$ consisting of bipartite graphs there exists an odd integer $k$ such that $ex(n,\mc{F} \cup \mc{C}_k) \sim z(n,\mc{F})$. They proved this when $\mc{F}={C_4}$ by showing that $ex(n,\{C_4,C_5\}) \sim z(n,C_4)$ . In this paper, we extend this result by showing that if $\ell \in \{2,3,5\}$ and $k > 2\ell$ is odd, then ${ex(n,\mc{C}_{2\ell} \cup {C_k}) \sim z(n,\mc{C}_{2\ell})$. Furthermore, if $k > 2\ell + 2$ is odd, then for infinitely many $n$ we show that the extremal $\mc{C}_{2\ell} \cup \{C_k\}$-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd $k < 2\ell$ , and furthermore the asymptotic result does not hold when $(\ell,k)$ is $(3,3)$ , $(5,3)$ or $(5,5)$ . Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest.

preprint2010arXiv

Cycles in Sparse Graphs II

The {\em independence ratio} of a graph $G$ is defined by $ι(G) := \sup_{X \subset V(G)} \frac{|X|}{α(X)},$ where $α(X)$ is the independence number of the subgraph of $G$ induced by $X$ . The independence ratio is a relaxation of the chromatic number $χ(G)$ in the sense that $χ(G) \geq ι(G)$ for every graph $G$ , while for many natural classes of graphs these quantities are almost equal. In this paper, we address two old conjectures of Erdős on cycles in graphs with large chromatic number and a conjecture of Erdős and Hajnal on graphs with infinite chromatic number.

preprint2010arXiv

The de Bruijn-Erdos Theorem for hypergraphs

Fix integers $n \ge r \ge 2$ . A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, ..., A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$ . Clique partitions are related to design theory, coding theory, projective geometry, and extremal combinatorics. Let $\cp(n,r)$ denote the minimum size of a clique partition of ${[n] \choose r}$ . A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$ and also determines the extremal configurations. In this paper we study $\cp(n,r)$, and show in general that for each fixed $r \geq 3$ , \[\cp(n,r) \geq (1 + o(1))n^{r/2} \quad \quad {as}n \to \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$, and prove this conjecture in a very strong sense for $r = 3$ by giving a characterization of optimal clique partitions of ${[n] \choose 3}$ for infinitely many $n$ . Precisely, when $n = q^2 + 1$ and $q$ is a prime power, we show \[ \cp(n,3) = n\sqrt{n-1} \] and characterize those clique partitions achieving equality. We also give an absolute lower bound $\cp(n,r) \geq {n \choose r}/{q + r - 1 \choose r}$ when $n = q^2 + q + r - 1$ , and for each $r$ characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of $\cp(n,r)$ to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.

Jacques Verstraete

Research overview

Is this your work?

19 publications

Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

Set-coloring Ramsey numbers via codes

A generalization of the Bollobás set pairs inequality

Triangle-free Subgraphs of Hypergraphs

The extremal function for cycles of length $\ell$ mod $k$

A survey of Turán problems for expansions

The number of trees in a graph

Cycles in triangle-free graphs of large chromatic number

On Coupon Colorings of Graphs

On sets of integers with restrictions on their products

Turan Problems and Shadows II: Trees

Turan Problems and Shadows III: expansions of graphs

A counterexample to sparse removal

Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

Small maximal partial ovoids in generalized quadrangles

Turan numbers for bipartite graphs plus an odd cycle

On a conjecture of Erdos and Simonovits: Even Cycles

Cycles in Sparse Graphs II

The de Bruijn-Erdos Theorem for hypergraphs

See the researcher in context

Building this map preview

Jacques Verstraete

Research overview

Is this your work?

19 publications

Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

Set-coloring Ramsey numbers via codes

A generalization of the Bollobás set pairs inequality

Triangle-free Subgraphs of Hypergraphs

The extremal function for cycles of length ℓ\ellℓ mod kkk

A survey of Turán problems for expansions

The number of trees in a graph

Cycles in triangle-free graphs of large chromatic number

On Coupon Colorings of Graphs

On sets of integers with restrictions on their products

Turan Problems and Shadows II: Trees

Turan Problems and Shadows III: expansions of graphs

A counterexample to sparse removal

Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

Small maximal partial ovoids in generalized quadrangles

Turan numbers for bipartite graphs plus an odd cycle

On a conjecture of Erdos and Simonovits: Even Cycles

Cycles in Sparse Graphs II

The de Bruijn-Erdos Theorem for hypergraphs

See the researcher in context

Building this map preview

The extremal function for cycles of length $\ell$ mod $k$