BZPEER

preprint2021arXiv

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

A graph $G$ is $F$ -saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$ . We prove that for $s \geq 3$ and $t \geq 2$ , the minimum number of copies of $K_{1,t}$ in a $K_s$ -saturated graph is $Θ( n^{t/2})$ . More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s \geq 4$ and $t \geq 3$ , the minimum number of copies of $K_{2,t}$ in an $n$ -vertex $K_s$ -saturated graph is at least $Ω( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$ . These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$ -saturated graph are also obtained, but finding an asymptotic formula remains open.

preprint2020arXiv

Regular Turán numbers of complete bipartite graphs

Let $\mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$ -vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $\mathrm{rex}(n, F)$ , that are best possible up to a constant factor, when $F$ is one of $C_4$ , $K_{2,t}$ , $K_{3,3}$ or $K_{s,t}$ when $t>s!$ .

preprint2016arXiv

A Szemerédi-Trotter type theorem, sum-product estimates in finite quasifields, and related results

We prove a Szemerédi-Trotter type theorem and a sum-product estimate in the setting of finite quasifields. These estimates generalize results of the fourth author, of Garaev, and of Vu. We generalize results of Gyarmati and Sárközy on the solvability of the equations $a + b = cd$ and $ab + 1 = cd$ over a finite field. Other analogous results that are known to hold in finite fields are generalized to finite quasifields.

preprint2016arXiv

Independent sets in polarity graphs

Given a projective plane $Σ$ and a polarity $θ$ of $Σ$ , the corresponding polarity graph is the graph whose vertices are the points of $Σ$ , and two distinct points $p_1$ and $p_2$ are adjacent if $p_1$ is incident to $p_2^{ θ}$ in $Σ$ . A well-known example of a polarity graph is the Erdős-Rényi orthogonal polarity graph $ER_q$ , which appears frequently in a variety of extremal problems. Eigenvalue methods provide an upper bound on the independence number of any polarity graph. Mubayi and Williford showed that in the case of $ER_q$ , the eigenvalue method gives the correct upper bound in order of magnitude. We prove that this is also true for other families of polarity graphs. This includes a family of polarity graphs for which the polarity is neither orthogonal nor unitary. We conjecture that any polarity graph of a projective plane of order $q$ has an independent set of size $Ω(q^{3/2})$ . Some related results are also obtained.

preprint2016arXiv

Upper bounds for $B_h[g]$ -sets with small $h$

For $g \geq 2$ and $h \geq 3$ , we give small improvements on the maximum size of a $B_h[g]$ -set contained in the interval $\{1,2, \dots , N \}$ . In particular, we show that a $B_3[g]$ -set in $\{1,2, \dots , N \}$ has at most $(14.3 g N)^{1/3}$ elements. The previously best known bound was $(16 gN)^{1/3}$ proved by Cilleruelo, Ruzsa, and Trujillo. We also introduce a related optimization problem that may be of independent interest.

preprint2015arXiv

A path Turan problem for infinite graphs

Let $G$ be an infinite graph whose vertex set is the set of positive integers, and let $G_n$ be the subgraph of $G$ induced by the vertices $\{1,2, \dots , n \}$ . An increasing path of length $k$ in $G$ , denoted $I_k$ , is a sequence of $k+1$ vertices $1 \leq i_1 < i_2 < \dots < i_{k+1}$ such that $i_1, i_2, \ldots, i_{k+1}$ is a path in $G$ . For $k \geq 2$ , let $p(k)$ be the supremum of $\liminf_{ n \rightarrow \infty} \frac{ e(G_n) }{n^2}$ over all $I_k$ -free graphs $G$ . In 1962, Czipszer, Erdős, and Hajnal proved that $p(k) = \frac{1}{4} (1 - \frac{1}{k})$ for $k \in \{2,3 \}$ . Erdős conjectured that this holds for all $k \geq 4$ . This was disproved for certain values of $k$ by Dudek and Rödl who showed that $p(16) > \frac{1}{4} (1 - \frac{1}{16})$ and $p(k) > \frac{1}{4} + \frac{1}{200}$ for all $k \geq 162$ . Given that the conjecture of Erdős is true for $k \in \{2,3 \}$ but false for large $k$ , it is natural to ask for the smallest value of $k$ for which $p(k) > \frac{1}{4} ( 1 - \frac{1}{k} )$ . In particular, the question of whether or not $p(4) = \frac{1}{4} ( 1 - \frac{1}{4} )$ was mentioned by Dudek and Rödl as an open problem. We solve this problem by proving that $p(4) \geq \frac{1}{4} (1 - \frac{1}{4} ) + \frac{1}{584064}$ and $p(k) > \frac{1}{4} (1 - \frac{1}{k})$ for $4 \leq k \leq 15$ . We also show that $p(4) \leq \frac{1}{4}$ which improves upon the previously best known upper bound on $p(4)$ . Therefore, $p(4)$ must lie somewhere between $\frac{3}{16} + \frac{1}{584064}$ and $\frac{1}{4}$

preprint2015arXiv

Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

In this note, we show that for any $m \in \{1,2, \dots , q +1 \}$ , if $G$ is a polarity graph of a projective plane of order $q$ that has an oval, then $G$ contains a subgraph on $m + \binom{m}{2}$ vertices with $m^2+\frac{m^4}{8q} - O ( \frac{m^4}{q^{3/2} } +m )$ edges. As an application, we give the best known lower bounds on the Turán number $\mathrm{ex}(n, C_4)$ for certain values of $n$ . In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning $\mathrm{ex}(q^2-q-2, C_4)$ where $q$ is a power of $2$ .

preprint2014arXiv

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

For a prime power $q$ , let $ER_q$ denote the Erdős-Rényi orthogonal polarity graph. We prove that if $q$ is an even power of an odd prime, then $χ( ER_{q}) \leq 2 \sqrt{q} + O ( \sqrt{q} / \log q)$ . This upper bound is best possible up to a constant factor of at most 2. If $q$ is an odd power of an odd prime and satisfies some condition on irreducible polynomials, then we improve the best known upper bound for $χ(ER_{q})$ substantially. We also show that for sufficiently large $q$ , every $ER_q$ contains a subgraph that is not 3-chromatic and has at most 36 vertices.

preprint2014arXiv

Orthogonal polarity graphs and Sidon sets

Determining the maximum number of edges in an $n$ -vertex $C_4$ -free graph is a well-studied problem that dates back to a paper of Erdős from 1938. One of the most important families of $C_4$ -free graphs are the Erdős-Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose-Chowla Sidon set is isomorphic to a large induced subgraph of the Erdős-Rényi orthogonal polarity graph. Using this isomorphism we prove that the Petersen graph is a subgraph of every sufficiently large Erdős-Rényi orthogonal polarity graph.

preprint2014arXiv

Sidon Sets and graphs without 4-cycles

The problem of determining the maximum number of edges in an $n$ -vertex graph that does not contain a 4-cycle has a rich history in extremal graph theory. Using Sidon sets constructed by Bose and Chowla, for each odd prime power $q$ we construct a graph with $q^2 - q - 2$ vertices that does not contain a 4-cycle and has at least $\frac{1}{2}q^3 - q^2 - O(q^{3/4})$ edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Turán number $\mathrm{ex}(q^2 - q - 2, C_4)$ .

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

Bounds for generalized Sidon sets

Let $Γ$ be an abelian group and $g \geq h \geq 2$ be integers. A set $A \subset Γ$ is a $C_h[g]$ -set if given any set $X \subset Γ$ with $|X| = k$ , and any set $\{ k_1 , \dots , k_g \} \subset Γ$ , at least one of the translates $X+ k_i$ is not contained in $A$ . For any $g \geq h \geq 2$ , we prove that if $A \subset \{1,2, \dots ,n \}$ is a $C_h[g]$ -set in $\mathbb{Z}$ , then $|A| \leq (g-1)^{1/h} n^{1 - 1/h} + O(n^{1/2 - 1/2h})$ . We show that for any integer $n \geq 1$ , there is a $C_3 [3]$ -set $A \subset \{1,2, \dots , n \}$ with $|A| \geq (4^{-2/3} + o(1)) n^{2/3}$ . We also show that for any odd prime $p$ , there is a $C_3[3]$ -set $A \subset \mathbb{F}_p^3$ with $|A| \geq p^2 - p$ , which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer $h \geq 3$ , there is a $C_h[h! +1]$ -set $A \subset \{1,2, \dots , n \}$ with $|A| \geq ( c_h +o(1))n^{1-1/h}$ . A set $A$ is a \emph{weak $C_h[g]$ -set} if we add the condition that the translates $X +k_1, \dots , X + k_g$ are all pairwise disjoint. We use the probabilistic method to construct weak $C_h[g]$ -sets in $\{1,2, \dots , n \}$ for any $g \geq h \geq 2$ . Lastly we obtain upper bounds on infinite $C_h[g]$ -sequences. We prove that for any infinite $C_h[g$ ]-sequence $A \subset \mathbb{N}$ , we have $A(n) = O ( n^{1 - 1/h} ( \log n )^{ - 1/h} )$ for infinitely many $n$ , where $A(n) = | A \cap \{1,2, \dots , n \}|$ .

preprint2013arXiv

Infinite Turán problems for bipartite graphs

We consider an infinite version of the bipartite Turán problem. Let $G$ be an infinite graph with $V(G) = \mathbb{N}$ and let $G_n$ be the $n$ -vertex subgraph of $G$ induced by the vertices $\{1,2, \dots, n \}$ . We show that if $G$ is $K_{2,t+1}$ -free then for infinitely many $n$ , $e(G_n) \leq 0.471 \sqrt{t} n^{3/2}$ . Using the $K_{2,t+1}$ -free graphs constructed by Füredi, we construct an infinite $K_{2,t+1}$ -free graph with $e(G_n) \geq 0.23 \sqrt{t}n^{3/2}$ for all $n \geq n_0$ .

preprint2013arXiv

k-fold Sidon sets

Let $k \geq 1$ be an integer. A set $A \subset \mathbb{Z}$ is a $k$ -fold Sidon set if $A$ has only trivial solutions to each equation of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0$ where $0 \leq |c_i | \leq k$ , and $c_1 + c_2 + c_3 + c_4 = 0$ . We prove that for any integer $k \geq 1$ , a $k$ -fold Sidon set $A \subset [N]$ has at most $(N/k)^{1/2} + O((Nk)^{1/4})$ elements. Indeed we prove that given any $k$ positive integers $c_1<\cdots <c_k$ , any set $A\subset [N]$ that contains only trivial solutions to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$ , has at most $(N/k)^{1/2}+O((c_k^2N/k)^{1/4})$ elements. On the other hand, for any $k \geq 2$ we can exhibit $k$ positive integers $c_1,\dots, c_k$ and a set $A\subset [N]$ with $|A|\ge (\frac 1k+o(1))N^{1/2}$ , such that $A$ has only trivial solutions to $c_i(x_1 - x_2) = c_j (x_3 - x_4)$ for each $1 \le i \le j\le k$ .

preprint2013arXiv

Upper and lower bounds on $B_k^+$ -sets

Let $G$ be an abelian group. A set $A \subset G$ is a \emph{ $B_k^+$ -set} if whenever $a_1 + \dots + a_k = b_1 + \dots + b_k$ with $a_i, b_j \in A$ there is an $i$ and a $j$ such that $a_i = b_j$ . If $A$ is a $B_k$ -set then it is also a $B_k^+$ -set but the converse is not true in general. Determining the largest size of a $B_k$ -set in the interval $\{1, 2, \dots, N \} \subset \integers$ or in the cyclic group $\integers_N$ is a well studied problem. In this paper we investigate the corresponding problem for $B_k^+$ -sets. We prove non-trivial upper bounds on the maximum size of a $B_k^+$ -set contained in the interval $\{1, 2, \dots, N \}$ . For odd $k \geq 3$ , we construct $B_k^+$ -sets that have more elements than the $B_k$ -sets constructed by Bose and Chowla. We prove a $B_3^+$ -set $A \subset \integers_N$ has at most $(1 + o(1))(8N)^{1/3}$ elements. Finally we obtain new upper bounds on the maximum size of a $B_k^*$ -set $A \subset \{1,2, \dots, N \}$ , a problem first investigated by Ruzsa.

Craig Timmons

Research overview

Is this your work?

15 publications

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

Regular Turán numbers of complete bipartite graphs

A Szemerédi-Trotter type theorem, sum-product estimates in finite quasifields, and related results

Independent sets in polarity graphs

Upper bounds for $B_h[g]$ -sets with small $h$

A path Turan problem for infinite graphs

Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Orthogonal polarity graphs and Sidon sets

Sidon Sets and graphs without 4-cycles

A counterexample to sparse removal

Bounds for generalized Sidon sets

Infinite Turán problems for bipartite graphs

k-fold Sidon sets

Upper and lower bounds on $B_k^+$ -sets

See the researcher in context

Building this map preview

Craig Timmons

Research overview

Is this your work?

15 publications

Minimizing the number of complete bipartite graphs in a KsK_sKs​-saturated graph

Regular Turán numbers of complete bipartite graphs

A Szemerédi-Trotter type theorem, sum-product estimates in finite quasifields, and related results

Independent sets in polarity graphs

Upper bounds for Bh[g]B_h[g]Bh​[g]-sets with small hhh

A path Turan problem for infinite graphs

Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Orthogonal polarity graphs and Sidon sets

Sidon Sets and graphs without 4-cycles

A counterexample to sparse removal

Bounds for generalized Sidon sets

Infinite Turán problems for bipartite graphs

k-fold Sidon sets

Upper and lower bounds on Bk+B_k^+Bk+​-sets

See the researcher in context

Building this map preview

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

Upper bounds for $B_h[g]$ -sets with small $h$

Upper and lower bounds on $B_k^+$ -sets