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 For an oriented graph , let denote the size of aminimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any ‐edge oriented graph satisfies . We observe that if an oriented graph has a fixed forbidden subgraph , the bound is sharp as a function of if is not bipartite, but the exponent in the lower order term can be improved if is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear‐time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/S0963548321000341
