TL;DR
This paper investigates the maximum number of edges a bipartite graph can have while still being "linklessly embeddable" in 3D space. The authors prove that such graphs with $n \ge 5$ vertices have at most $3n-10$ edges, unless they are a specific complete bipartite graph ($K_{3,n-3}$). This result refines a known bound for general graphs and contributes to understanding the structural properties of linklessly embeddable graphs.
What Problem Does This Paper Address?
The paper tackles a question in graph theory concerning the "extremal function" for a specific class of graphs: bipartite, linklessly embeddable graphs. An embedding of a graph in 3-space is considered "linkless" if any two disjoint cycles in the embedding can be separated by a 3D "ball." This property is related to whether a graph contains certain forbidden minors, like those from the Petersen family. For general graphs (not necessarily bipartite), it's known that linklessly embeddable graphs on $n$ vertices have at most $4n-10$ edges. For bipartite graphs, a tighter bound is suspected. The authors aim to establish this tighter bound, specifically proving that for $n \ge 5$, the maximum number of edges is $3n-10$, with a specific exception.
Methods
The proof is primarily a constructive, contradiction-based argument. The authors start by assuming a counterexample exists (a bipartite linklessly embeddable graph with more than $3n-10$ edges, violating the theorem) and then systematically derive contradictions by analyzing the graph's structure. Key techniques include:
- Structural Analysis: Examining vertices of low degree (specifically 4 and 5) and their neighborhoods.
- Separations and Super-separations: Decomposing the graph into smaller parts (separations) and analyzing relationships between these parts and their minors (super-separations). This is a standard technique in extremal graph theory.
- Forbidden Minors: Leveraging the connection between linkless embeddability and forbidden minors (specifically, members of the Petersen family, and $K_6$, $K_{3,3}$, $K_{4,4}$, $K_{4,4}'$). The absence of these minors is crucial.
- Lemmas and Case Analysis: The proof is built upon a series of carefully crafted lemmas that progressively constrain the structure of the hypothetical counterexample. This involves detailed case analysis based on vertex degrees, set sizes, and graph properties.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The $3n-10$ Bound is Tight: The paper establishes that $3n-10$ is indeed the sharp upper bound for the number of edges in most bipartite linklessly embeddable graphs on $n \ge 5$ vertices.
- The $K_{3,n-3}$ Exception: The specific complete bipartite graph $K_{3,n-3}$ is identified as the unique graph (up to isomorphism) that can exceed this bound while remaining linklessly embeddable. This highlights the importance of specific graph structures in extremal problems.
- Role of Low-Degree Vertices: The proof heavily relies on analyzing vertices of degree 4 and 5. The behavior of their neighbors and common neighbors is critical in deriving contradictions.
- Connection to Forbidden Minors: The proof implicitly or explicitly uses the fact that linklessly embeddable graphs are characterized by the absence of certain minors. The analysis often leads to the discovery of these forbidden minors in the hypothetical counterexample.
Key Results
The main result is Theorem 1.1: Every bipartite linklessly embeddable graph on $n \ge 5$ vertices has at most $3n-10$ edges, unless it is isomorphic to the complete bipartite graph $K_{3,n-3}$.
The proof of this theorem is achieved through Theorem 3.1, which states that every bipartite graph on $n \ge 5$ vertices with no $K_6$, $K_{3,3}$, $K_{4,4}$, or $K_{4,4}'$ minor has at most $3n-10$ edges, unless it is isomorphic to $K_{3,n-3}$. The equivalence of linkless embeddability and the absence of Petersen family minors (which includes $K_6$ and $K_{3,3}$) is established in Theorem 1.2, thus linking these results.
Limitations and Future Work
- Specific Graph Class: The results are specific to bipartite linklessly embeddable graphs. Extending these bounds to general linklessly embeddable graphs or other graph classes remains an area of interest.
- Conjectures: The paper presents several related conjectures, including:
- Conjecture 1.9: Every triangle-free linklessly embeddable graph on $n \ge 5$ vertices has at most $3n-10$ edges (unless it's $K_{3,n-3}$).
- Conjecture 1.10: Every linklessly embeddable graph on $n \ge 7$ vertices with $t$ triangles has at most $3n-9+t/3$ edges.
- Conjecture 1.8: For bipartite graphs with a specific Colin de Verdière parameter $\mu(G) < p$, bounds on edges are explored.
- Algorithmic Implications: While the paper focuses on extremal bounds, understanding these structural properties could potentially lead to algorithms for recognizing or constructing such graphs.
Summary updated