Search for: All records

Abstract We show that for every integer and large , every properly edge‐colored graph on vertices with at least edges contains a rainbow subdivision of . This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs. 

Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte. 

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 containingC_2k, the cycle of length 2k, isO(n^1+1/k). Simonovits established a corresponding supersaturation result forC_2k’s, showing that there exist positive constantsC,cdepending only onksuch that everyn-vertex graphGwithe(G)⩾Cn^1+1/kcontains at leastc(e(G)/v(G))^2kcopies ofC_2k, 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. 

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$ .