Bipartite Turán problem on graph gluing

Zichao Dong, Jun Gao, Hong Liu · 2025

Read Bipartite Turán problem on graph gluing by Zichao Dong, Jun Gao, Hong Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12953.txt.

Introduction

Zichao Dong, Jun Gao, and Hong Liu study what happens when two networks are glued into one, in a 2025 paper. The head of the hosted text calls the topic bipartite Turán problems via graph gluing. Gluing means picking one point in each network and merging the two points into one. The team asks how many links the joined network can hold before a set pattern must appear.

Their main finding links the glued case to a much older question posed by Erdős and Simonovits. When both halves are copies of the same two-sided network, glued at matching points, the limit on links grows at the same rate as for one half alone. As a side result, the team gives a short, self-contained disproof of a guess by Erdős. The paper is pure math, proved rather than measured.

Catalog record

CREATORZichao Dong, Jun Gao, Hong Liu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12953

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bipartite Turán problem on graph gluing Zichao Dong, Jun Gao, Hong Liu Abstract For graphs H 1 H_{1} and H 2 H_{2} , if we glue them by identifying a given pair of vertices u ∈ V ⁡ ( H 1 ) u\in V(H_{1}) and v ∈ V ⁡ ( H 2 ) v\in V(H_{2}) , what is the extremal number of the resulting graph H 1 u ⊙ H 2 v H_{1}^{u}\odot H_{2}^{v} ? In this paper, we study this problem and show that interestingly it is equivalent to an old question of Erdős and Simonovits on the Zarankiewicz problem. When H 1 , H 2 H_{1},H_{2} are copies of a same bipartite graph H H and u , v u,v come from a same part, we prove that ex ⁡ ( n , H 1 u ⊙ H 2 v ) = Θ ⁡ ( ex ⁡ ( n , H ) ) \mathrm{ex}(n,H_{1}^{u}\odot H_{2}^{v})=\Theta\bigl(\mathrm{ex}(n,H)\bigr) . As a corollary, we provide a short self-contained disproof of a conjecture of Erdős, which was recently disproved by Janzer. 1 Introduction The extremal number of a graph H , denoted by \mathrm{ex}(n,H) , is the maximum number of edges in an n -vertex H -free graph. Determining this function is one of the most important topics in extremal graph theory, originating from the classical work of Mantel [ 16 ] and Turán [ 18 ] . For any graph H and n\to\infty , the celebrated Erdős–Stone–Simonovits theorem [ 6 , 8 ] states that \mathrm{ex}(n,H)=\Bigl(1-\frac{1}{\chi(H)}+o(1)\Bigr)\cdot\frac{n^{2}}{2}, where \chi(H) is the chromatic number of H . This result asymptotically resolves the problem for every non-bipartite H . However, for a bipartite H , it only shows \mathrm{ex}(n,H)=o(n^{2}) . Complete comprehension of the behavior of \mathrm{ex}(n,H) for bipartite H remains elusive. The order of magnitude is known only for a handful of bipartite graphs. For more details, we refer the readers to the Füredi–Simonovits survey [ 10 ] . As every graph can be built from smaller ones, a natural approach is to study how graph operations could affect the extremal function for bipartite graphs. In this paper, we investigate the following simple gluing operation: given bipartite H_{1},H_{2} and vertices u\in V(H_{1}),\,v\in V(H_{2}) , denote by H_{1}^{u}\odot H_{2}^{v} the graph built from gluing H_{1} and H_{2} by identifying u and v . Throughout this paper, the big-oh, little-oh, and big-theta notations always hide the n\to\infty limit process. When a gluing H_{1}^{u}\odot H_{2}^{v} is considered, we implicitly assume that the vertex sets V(H_{1}),V(H_{2}) are disjoint. We propose the following conjecture. Conjecture 1.1 . If H_{1},H_{2} are bipartite graphs and u\in V(H_{1}),\,v\in V(H_{2}) , then \mathrm{ex}(n,H_{1}^{u}\odot H_{2}^{v})=\Theta\bigl(\mathrm{ex}(n,H_{1})+\mathrm{ex}(n,H_{2})\bigr). The following special case of 1.1 when H_{1},H_{2} are isomorphic is particularly interesting, as we shall see that it is closely related to the famous Zarankiewicz problem. Conjecture 1.2 . If H_{1},H_{2} are two copies of a bipartite graph H and u\in V(H_{1}),\,v\in V(H_{2}) , then \mathrm{ex}(n,H_{1}^{u}\odot H_{2}^{v})=\Theta\bigl(\mathrm{ex}(n,H)\bigr). To explain the connection to the Zarankiewicz problem, define \mathrm{ex}(n,m,H) as the maximum number of edges of a subgraph of the complete bipartite graph K_{n,m} that does not contain H as a subgraph. The Zarankiewicz problem is an asymmetric version: given a bipartition (L,R) of a bipartite graph H , its Zarankiewicz number, denoted by Z(n,m,H[L,R]) , is the maximum number of edges of a subgraph of K_{n,m} that does not contain H as a subgraph with L in the part of size n and R in the part of size m . When n=m , we write Z(n,n,H)\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}Z(n,n,H[L,R])=Z(n,n,H[R,L]) for ease of notations. It follows directly from the definitions that Z(n,n,H)\geq\mathrm{ex}(n,n,H) and \mathrm{ex}(2n,H)\geq\mathrm{ex}(n,n,H) . Since every graph contains a balanced bipartite subgraph with at least half of its edges, we have that \mathrm{ex}(n,n,H)\geq\frac{1}{2}\mathrm{ex}(2n,H) . For the relationship between \mathrm{ex}(n,n,H) and Z(n,n,H) , Erdős and Simonovits [ 17 ] made the following conjecture (see [ 10 , Conjecture 2.12] ). Conjecture 1.3 ( [ 17 ] ) . If H is a bipartite graph, then Z(n,n,H)=\Theta\bigl(\mathrm{ex}(n,n,H)\bigr). Let H_{1} and H_{2} be two copies of a bipartite graph H with bipartition (A,B) . For any u\in A and v\in B , we have Z(n,n,H)\leq\mathrm{ex}(n,n,H_{1}^{u}\odot H_{2}^{v}) . So, 1.2 implies 1.3 . Our first result shows that these three conjectures are in fact equivalent to each other. Theorem 1.4 . 1.1 , 1.2 , and 1.3 are all equivalent. Considering 1.2 , our next result states that if the two vertices we merge come from the same part of the graph, then the conjecture holds. Theorem 1.5 . Let H_{1} and H_{2} be two copies of a bipartite graph H with bipartition (A,B) . If vertices u\in V(H_{1}),\,v\in V(H_{2}) satisfy that u,v are both from A or both from B , then \mathrm{ex}(n,H_{1}^{u}\odot H_{2}^{v})=\Theta\bigl(\mathrm{ex}(n,H)\bigr). Theorem 1.5 is related to yet another old conjecture of Erdős and Simonovits. For any positive integer r , recall that a graph is r -degenerate if each of its subgraphs has minimum degree at most r . Erdős and Simonovits [ 4 ] proposed the conjecture below. Conjecture 1.6 ( [ 2 ] ) . For a bipartite H , we have \mathrm{ex}(n,H)=O(n^{3/2}) if and only if H is 2 -degenerate. Erdős was particularly interested in 1.6 as he stated the problem several times [ 2 , 3 , 4 , 5 ] . Moreover, he offered $250 for a proof and $500 for a disproof. 1.6 has the following extension. Conjecture 1.7 . For a bipartite H , we have \mathrm{ex}(n,H)=O(n^{2-1/r}) if and only if H is r -degenerate. Historically, the “if” direction of 1.7 was made by Erdős [ 1 ] . As for the other direction, a stronger conjecture that any bipartite H of minimum degree at least r+1 has \mathrm{ex}(n,H)=\Omega(n^{2-1/r+\varepsilon}) was proposed by Erdős and Simonovits [ 5 ] . The “only if” direction was recently disproved by Janzer, first for every r\geq 3 in [ 13 ] , and then for r=2 in [ 12 ] , via delicate and involved explicit constructions. As an application of Theorem 1.5 , we present here a very short disproof of 1.7 for all r\geq 2 at once by arguing that the “if” and the “only if” direction cannot hold simultaneously. Disproof of Conjecture 1.7 assuming Theorem 1.5 . We first prove that for every r\geq 2 , there exist bipartite r -degenerate graphs with exactly one vertex of degree r . Construct in three steps: • To start, we take a copy of K_{r,r+1} whose bipartition is (X,Y) such that |X|=r and |Y|=r+1 . • For all but one r -element subsets S\subseteq Y , we add a unique vertex z_{S} whose neighborhood is S . • Finally, we add yet another new vertex w which is adjacent to exactly all those vertices z_{S} . We obtain an r -degenerate graph where w is the only degree- r vertex. See Figure 1 for the r=2 case. Pick a bipartite r -degenerate H with exactly one vertex of degree r . Assuming the “if” direction of 1.6 , we have \mathrm{ex}(n,H)=O(n^{2-1/r}) . Take two copies H_{1},H_{2} of H and let u,v be the unique degree- r vertices of H_{1},H_{2} , respectively. Write H^{*}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}H_{1}^{u}\odot H_{2}^{v} .

Read the complete text