Combinatorics Probability Computing · 2021 · 17 citations · 21 references
Natural SciencesComputer ScienceMathematicsCombinatoricsGeometryNumber TheoryCombinatorial Number TheoryGraph TheoryErdős - Turán ConjecturesErdős-turán Conjecture
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$ .
21
On the structure of linear graphs
Paul Erdős, A. H. Stone · Bulletin of the American Mathematical Society · 1946 · 866 citations · Full text
On Graphs that do not Contain a Thomsen Graph
William G. Brown · Canadian Mathematical Bulletin · 1966 · 390 citations · Full text
On the combinatorial problems which I would most like to see solved
P. Erdös · COMBINATORICA · 1981 · 321 citations
Norm-graphs and bipartite tur�n numbers
J�nos Koll�r, Lajos R�nyai, Tibor Szab� · COMBINATORICA · 1996 · 162 citations