Bipartite Turán number of paths and other trees

Basic Information

• Paper ID: 2511.07374
• Title: Bipartite Turán number of paths and other trees
• Authors: Marthe Bonamy, Théotime Leclere, Timothé Picavet
• Affiliations: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
• Classification: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
• Publication Date: November 11, 2025
• Paper Link: https://arxiv.org/abs/2511.07374

Abstract

This paper completely resolves a recently posed question by Caro, Patkós, and Tuza: determining the exact maximum number of edges in connected bipartite graphs as a function of the longest path length and the number of vertices on each side of the bipartition. Previously, this problem was known only for balanced bipartitions with longest path length at most 5. The paper also discusses possible generalizations by replacing "paths" with specific tree types.

Research Background and Motivation

Problem Context

1. Classical Turán Problem: Turán's theorem determines the maximum number of edges in an n-vertex graph containing no complete subgraph of a given order, initiating systematic study of forbidden subgraph extremal problems.
2. Limitations of Erdős-Stone Theorem: This theorem asymptotically gives Turán numbers for all non-bipartite forbidden graphs, but provides no information for the bipartite case.
3. Specificity of Bipartite Graphs: The Turán problem for bipartite graphs remains open, spawning several core conjectures, most notably the Erdős-Sós conjecture: an n-vertex graph excluding a k-vertex tree has at most (k-2)n/2 edges.
4. Connected Bipartite Graphs: Caro, Patkós, and Tuza CPT25 recently focused on the case where the host graph is both bipartite and connected, introducing the notation ex_{b,c}(a,b,H) to denote the maximum number of edges in a connected bipartite graph with parts of sizes a and b containing no H as a subgraph.

Research Motivation

• Limitations of Known Results: CPT25 solved only cases for all trees with 6 or fewer vertices, double stars, and certain spider graphs, particularly knowing only ex_{b,c}(n,n,P₅) = ex_{b,c}(n,n,P₆) = 2n-1
• Open Problem: Determining ex_{b,c}(n,n,P_k) for arbitrary paths P_k, at least asymptotically
• Generalization Needs: Studying ex_{b,c} values for specific tree families

Core Contributions

1. Complete Resolution of Path Problem: For all paths P_k, providing exact values of ex_{b,c}(a,b,P_k), not merely asymptotic values, applicable to unbalanced bipartite graphs (Main Theorem 1.5)
2. Extension to Broom Graphs: For broom graphs S_{p,d}* (combination of a path of length p and a star with d branches), providing exact values when the star dominates the path (Theorem 1.6)
3. Upper Bound Results: When the star is at most half the path size, providing upper bounds (Theorem 1.7)
4. Technical Innovation: Developing new techniques for handling connected bipartite graphs, including existence lemmas for critical vertices and inductive frameworks

Methodology Details

Problem Definition

Definition 1.1: For fixed integers a, b and graph H, ex_{b,c}(a,b,H) is the maximum number of edges in a connected bipartite graph with parts of sizes a and b containing no H as a subgraph.

This paper primarily studies:

• Input: Path length k, bipartition sizes a, b
• Output: Exact value of ex_{b,c}(a,b,P_k)
• Constraints: Graph must be connected, bipartite, and H-free

Core Theorems

Theorem 1.5 (Main Result): For all k ≥ 3 and b ≥ a ≥ k, $\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a$

This formula demonstrates:

• Odd and even length paths have identical Turán numbers
• Edge count grows linearly with the larger part b, with coefficient (k-2)
• An additive correction term a exists

Proof Architecture

1. Lower Bound Construction (Section 2)

Proposition 2.1 provides constructive proof:

Construct a graph G with bipartition A = {u₁,...,u_a} and B = {v₁,...,v_b}:

• The first k-2 vertices in A are completely connected to all vertices in B (forming K_{k-2,b})
• The remaining a-(k-2) vertices in A serve as leaves, all connected to a specific vertex in B

Edge Count Calculation: $|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a$

P_{2k-1}-free Property Proof:

• The complete bipartite graph K_{k-2,b} has longest path with 2k-3 vertices
• Added leaves cannot extend paths, as they are degree-1 vertices

2. Upper Bound Proof (Section 3)

Uses induction with three key lemmas:

Lemma 3.2 (Existence of Small-Degree Vertices): In the larger part B, there exists a vertex x with degree ≤ k-2 whose removal preserves connectivity.

Proof Strategy:

• Use DFS tree to find a leaf b in B
• If d(b) ≤ k-2, set x = b
• If d(b) = k-1, path length must be 2k-2, forming a cycle
• Then find another vertex b' with degree ≤ k-2

Lemma 3.3 (Deletable Vertex Pairs in Balanced Graphs): For balanced bipartite graphs, there exist two vertices x, y such that d(x) + d(y) ≤ k-1 and their removal preserves connectivity and balance.

Proof uses endpoint analysis of longest path P:

• If endpoints are in different parts, may be directly applicable
• Otherwise, use DFS tree to find suitable leaf pairs

Lemma 3.4 (Base Case): When a = b = k, |E(G)| ≤ (k-1)² + 1.

Proof uses induction with key observation:

• Find minimum-degree non-cut vertex x
• Analyze remaining graph structure after removing x
• Use P_{2k}-free property to bound degree and structure

Main Theorem Proof:

• If b > a: Use Lemma 3.2 to delete one vertex, then induct
• If a = b > k: Use Lemma 3.3 to delete two vertices, then induct
• If a = b = k: Use Lemma 3.4

Results for Broom Graphs

Theorem 1.6: For k, d ≥ 2, when n ≥ d²/2 and d > 2k, $\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd$

Key technical lemmas:

Lemma 4.1: If the graph contains a vertex that is not an endpoint of a 2k-length path, then |E(G)| ≤ (k-1)(b+a)

Lemma 4.2: If |E(G)| ≥ k(b+a)+1, then every vertex has degree at most k+d-1

Proof combines these lemmas by deleting maximum-degree vertices and their neighbors, using connectivity and degree constraints to derive contradiction.

Experimental Setup

As a pure theoretical mathematics paper, this work contains no experimental section; all results are obtained through rigorous mathematical proof.

Experimental Results

Main Result Verification

Exact Formula for Paths:

• For P₅ and P₆: ex_{b,c}(n,n,P₅) = ex_{b,c}(n,n,P₆) = 2n-1
  • Using formula: k=3 gives (3-2)(n-1)+n = n-1+n = 2n-1 ✓
• For general P_k: Formula provides exact values for all cases, including unbalanced bipartite graphs

Broom Graph Results:

• When star dominates (d > 2k), Turán number equals nd
• Consistent with maximum degree constraints

Comparison with Known Results

1. Generalization of Proposition 1.2: This paper's results completely contain and generalize ex_{b,c}(n,n,P₅) = 2n-1 from CPT25
2. Generality Enhancement:
   • Extended from balanced to unbalanced graphs
   • Extended from specific small paths to arbitrary paths
   • From asymptotic to exact formulas

Related Work

Classical Results

1. Turán's Theorem Tur45: Extremal problem for complete graphs
2. Erdős-Stone Theorem ES46: Asymptotic Turán numbers for non-bipartite graphs
3. Gallai-Erdős GE59: Asymptotic results for connected graphs excluding fixed-size paths
4. Gyárfás-Rousseau-Schelp GRS84: Exact Turán numbers for bipartite graphs excluding fixed-size paths

Directly Related Work

Caro-Patkós-Tuza CPT25:

• Introduced ex_{b,c} notation
• Resolved cases for small trees (≤6 vertices)
• Resolved double stars and certain spider graphs
• Posed the problems solved in this paper

Independent Work

He-Salia-Zhu HSZ25: Authors note independent concurrent work submitted the same day with similar progress

Conclusions and Discussion

Main Conclusions

1. Complete Answer to Question 1.3: Provides exact values of ex_{b,c}(n,n,P_k) for all paths P_k, exceeding the asymptotic values requested
2. Partial Answer to Question 1.4: For broom graph family, provides exact values or bounds within specific parameter ranges
3. Methodological Contribution: Develops new technical framework for extremal problems on connected bipartite graphs

Limitations

1. Broom Graph Restrictions:
   • Theorem 1.6 requires d > 2k and n ≥ d²/2
   • Theorem 1.7 provides only upper bounds, not exact values
   • Intermediate cases (d ≈ k) remain incompletely resolved
2. General Tree Cases: Only paths and broom graphs addressed; broader tree families remain open
3. Technical Limitations: Some proof steps depend on specific structural properties, potentially difficult to generalize to more complex forbidden subgraphs

Future Directions

1. Refine Broom Graph Results: Determine exact values for all parameter ranges
2. Extend to Other Tree Families:
   • Complete characterization of spider graphs
   • Other special tree structures
3. Deeper Study of Unbalanced Cases: While this paper addresses a ≠ b, finer results may exist
4. Computational Complexity: Study algorithmic problems for determining whether given graphs achieve Turán bounds

In-Depth Evaluation

Strengths

1. Complete Resolution of Open Problem:
   • Not only answers Question 1.3 but provides stronger exact formulas than requested
   • Extends to unbalanced bipartite graphs, enhancing generality
2. Elegant Proof Techniques:
   • Lower bound construction is concise and clear
   • Upper bound proof's inductive structure is transparent
   • Key lemmas (3.2, 3.3, 3.4) are precisely stated and proven
3. Result Completeness:
   • For paths, exact formulas provided for all parameters
   • Formula form is simple: (k-2)(b-1)+a
   • Unified treatment of odd and even length paths
4. Writing Quality:
   • Clear paper structure with rigorous logic
   • Key steps supported by detailed sub-propositions
   • Figures (e.g., Figure 1) aid understanding of constructions
5. Technical Innovation:
   • Lemma 3.2 on existence of small-degree non-cut vertices is key insight
   • Characterization of deletable vertex pairs in balanced graphs (Lemma 3.3) has independent value
   • DFS tree usage throughout demonstrates effective application of classical tools

Weaknesses

1. Incomplete Broom Graph Results:
   • Parameter gap exists between Theorems 1.6 and 1.7
   • Theorem 1.7 provides only upper bound 2nk+1; gap from possible exact value unknown
   • Condition n ≥ d²/2 appears technically motivated, possibly not optimal
2. Complex Base Case Proof:
   • Lemma 3.4 (a=b=k case) proof occupies substantial space
   • Requires multiple sub-propositions (Claims 3.11-3.13)
   • More direct arguments may exist
3. Limited Generalizability:
   • Methods highly dependent on special structure of paths and broom graphs
   • Unclear how to apply techniques to general trees
   • No discussion of possible unified framework
4. Relationship to Independent Work:
   • Mentions HSZ25 independent work but lacks detailed comparison
   • Unclear whether technical methods are identical

Impact

1. Theoretical Contribution:
   • Completely resolves explicitly posed open problem
   • Provides new technical tools for connected bipartite Turán problems
   • Exactness of results establishes them as field benchmarks
2. Methodological Value:
   • Inductive framework potentially applicable to other forbidden subgraph problems
   • Key lemmas may be useful in other contexts
3. Subsequent Research:
   • Naturally motivates complete characterization of broom graphs
   • Inspires study of ex_{b,c} values for other tree families
   • May motivate research on non-connected cases
4. Verifiability:
   • As pure theoretical result, verifiable by proof inspection
   • Constructions are explicit and easily understood
   • Simple formulas facilitate application and citation

Applicable Scenarios

1. Theoretical Research:
   • Reference result for extremal graph theory researchers
   • Technical source for Turán-type problems
   • Case study for extremal problems under connectivity constraints
2. Related Problems:
   • Potentially insightful for Erdős-Sós conjecture research
   • Provides comparison for other trees' Turán numbers
   • Structural property research for connected bipartite graphs
3. Educational Value:
   • Demonstrates induction application in extremal combinatorics
   • Exemplifies DFS tree and path analysis
   • Complete case of matching upper and lower bounds

Key References

1. CPT25 Caro, Patkós, Tuza: Bipartite Turán number of trees - Poses problems solved in this paper
2. Tur45 Turán: On an extremal problem in graph theory - Foundational for Turán problems
3. ES46 Erdős, Stone: On the structure of linear graphs - Erdős-Stone theorem
4. GRS84 Gyárfás, Rousseau, Schelp: An extremal problem for paths in bipartite graphs - Exact Turán numbers for paths in bipartite graphs (without connectivity requirement)
5. HSZ25 He, Salia, Zhu: The connected bipartite Turán problem for long cycles and paths - Independent related work

Overall Assessment

This is a high-quality combinatorics paper that completely resolves an explicitly posed open problem with results stronger than requested. Proof techniques are elegant and innovative, with results exhibiting completeness and exactness. While generalization to arbitrary trees remains incomplete, the paper provides definitive answers for paths. This work makes substantial contributions to connected bipartite Turán problem research and is expected to become an important reference in the field.