An official website of the United States government
A longstanding conjecture of Erdos and Simonovits states that for every rational r between 1 and 2 there is a graph H such that the largest number of edges in an H-free graph on n vertices is \Theta(n^r). Answering a question raised by Jiang, Jiang and Ma, we show that the conjecture holds for all rationals of the form 2-a/b with b sufficiently large in terms of a.
more »
« less
On Turán exponents of bipartite graphs
Abstract A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $$r\in (1,2)$$ there exists a bipartite graph H such that $$\mathrm{ex}(n,H)=\Theta(n^r)$$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $$k\geq 2$$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $$k\geq 2$$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $$^{\prime}$$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $$^{\prime}$$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $$^{\prime}$$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ .
more »
« less
- Award ID(s):
- 1855542
- PAR ID:
- 10341101
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 31
- Issue:
- 2
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 333 to 344
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in ann-vertex graph not containingC2k, the cycle of length 2k, isO(n1+1/k). Simonovits established a corresponding supersaturation result forC2k’s, showing that there exist positive constantsC,cdepending only onksuch that everyn-vertex graphGwithe(G)⩾Cn1+1/kcontains at leastc(e(G)/v(G))2kcopies ofC2k, this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper we extend Simonovits' result to a supersaturation result ofr-uniform linear cycles of even length inr-uniform linear hypergraphs. Our proof is self-contained and includes ther= 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.more » « less
-
null (Ed.)Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $$G$$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $$k$$; in addition, if $$G$$ is $$2$$-connected and non-bipartite, then it contains cycles of all lengths modulo $$k$$. 2. For all $$k\geq 3$$, every $$k$$-connected graph contains a cycle of length zero modulo $$k$$. 3. Every $$3$$-connected non-bipartite graph with minimum degree at least $k+1$ contains $$k$$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $$k$$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible.more » « less
-
Abstract Given two k -graphs ( k -uniform hypergraphs) F and H , a perfect F -tiling (or F -factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H . For all complete k -partite k -graphs K , Mycroft proved a minimum codegree condition that guarantees a K -factor in an n -vertex k -graph, which is tight up to an error term o ( n ). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K (k) (1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.more » « less
-
A graph $$G$$ percolates in the $$K_{r,s}$$-bootstrap process if we can add all missing edges of $$G$$ in some order such that each edge creates a new copy of $$K_{r,s}$$, where $$K_{r,s}$$ is the complete bipartite graph. We study $$K_{r,s}$$-bootstrap percolation on the Erdős-Rényi random graph, and determine the percolation threshold for balanced $$K_{r,s}$$ up to a logarithmic factor. This partially answers a question raised by Balogh, Bollobás, and Morris. We also establish a general lower bound of the percolation threshold for all $$K_{r,s}$$, with $$r\geq s \geq 3$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/S0963548321000341
