Source-linked AI summary
Disproving the normal graph conjecture
Ararat Harutyunyan, Lucas Pastor, Stéphan Thomassé
TL;DR
The paper asks whether excluding induced C5, C7, and complement C7 characterizes normal graphs. It uses probabilistic constructions and covering arguments to show that this conjecture fails: a graph of girth at least 8 can be non-normal.
Problem
The Normal Graph Conjecture proposed that graphs without induced C5, C7, and complement C7 are normal.
Method
The proof constructs a sparse random graph and uses probabilistic properties together with star-covering and out-section arguments.
Results
There exists a graph of girth at least 8 that is not normal.
Takeaways & Limitations
The conjectured forbidden-induced-subgraph characterization of normal graphs is false, and the construction extends to graphs of arbitrary girth.
Abstract
from arXiv · showhide
A graph $G$ is called normal if there exist two coverings, $\mathbb{C}$ and $\mathbb{S}$ of its vertex set such that every member of $\mathbb{C}$ induces a clique in $G$, every member of $\mathbb{S}$ induces an independent set in $G$ and $C \cap S \neq \emptyset$ for every $C \in \mathbb{C}$ and $S \in \mathbb{S}$. It has been conjectured by De Simone and Körner in 1999 that a graph $G$ is normal if $G$ does not contain $C_5$, $C_7$ and $\overline{C_7}$ as an induced subgraph. We disprove this conjecture.
1. Introduction
The paper introduces normal graphs through intersecting clique and independent-set coverings, situates them alongside perfect graphs and graph entropy, and disproves the Normal Graph Conjecture with a stronger high-girth counterexample.
- Normal graphs: A normal graph has clique and independent-set coverings whose every pair of members intersects.This definition requires the clique covering and independent-set covering to cover the vertex set.
- Context: Normal graphs extend the perfect-graph framework and are closely related to graph entropy and co-normal products.Perfect graphs are defined by χ(H) = ω(H) for every induced subgraph, while normal graphs are closed under co-normal products.
- Related work: Known normal graph families include line-graphs of cubic graphs, circulants, some sparse graphs, all subcubic triangle-free graphs, and almost all fixed-degree regular graphs.The last result concerns almost all d-regular graphs when d is fixed.
- The conjecture: De Simone and Körner conjectured that every graph avoiding induced C5, C7, and complement C7 is normal.The conjecture was motivated by the known minimal non-normal examples described in the introduction.
- Contribution: The paper disproves the conjecture by proving that some graph of girth at least 8 is not normal.The proof is probabilistic and can be adapted to produce non-normal graphs of arbitrary girth.
2. Random graph properties
The section analyzes a sparse random graph G_n,p with p = n^-9/10, establishing bounds on short cycles, independent sets, degrees, and bipartite partial covers used later in the proof.
- Random graph model: G_n,p is the random graph on n vertices where every edge is chosen independently with probability p.The main construction uses p = n^-9/10, giving expected degree d = n^1/10.
- Properties of G: The chosen random graph has fewer than 4n^0.7 cycles of length at most seven with probability greater than 1/2.This follows from the bound P[X7 > 4n^0.7] < 1/2.
- Properties of G: For fixed c ≥ 10, the probability that the independence number reaches cn^0.9 log n is at most n^-c^2n^0.9 log n.The bound controls the size of independent sets in the sparse random graph.
- Probabilistic tools: Chernoff and Markov inequalities provide the concentration and probability bounds used for degree, edge-count, cycle, and independent-set estimates.These inequalities are introduced as the two basic probabilistic tools for the main theorem.
- Bipartite tools: The random bipartite-graph lemma guarantees near-expected edge density and a partial cover with probability at least 1 − e^-cp|A||B| when both sides exceed 10^100p^-1.The partial cover uses disjoint neighborhoods of specified size whose union covers at least one third of B.
3. Proof of Theorem 1.3
The proof constructs a sparse random graph with controlled short cycles and independence number, then shows that deleting vertices to eliminate short cycles cannot leave a normal graph.
- Star coverings: A normal triangle-free graph admits a star covering whose edge-union contains at most α(G) stars.The converse also holds: every graph admitting a star covering is normal.
- Star systems: For a star system, leaves whose centers form an out-section of Q* constitute an independent set.This follows by propagating membership through directed paths in the normal covering.
- Random-graph property: With p = n^-9/10, a random graph almost surely satisfies property JQ, which guarantees an out-section with at least n^0.95 private neighbors.The property applies to ten suitably sized vertex blocks after excluding a small set J.
- Random-graph construction: For sufficiently large n, some n-vertex graph has fewer than 4n^0.7 short cycles, α(G) < 10n^0.9 log n, maximum degree at most 2n^0.1, and property JQ.These properties are obtained simultaneously by the union bound.
- Contradiction setup: Assuming the short-cycle-free induced subgraph is normal yields a star covering with fewer than 10n^0.9 log n stars, enabling the construction of ten blocks of centers.Removing small stars and short-cycle vertices produces J with |J| < n^0.91, while domination forces |Q| > n^0.9/3.
- Final contradiction: Property JQ produces an out-section whose leaves form an independent set of size n^0.95, contradicting α(G) < 10n^0.9 log n.Private-neighbor edges belong to the star covering, so the private directed graph is a subdigraph of Q* and Lemma 3.2 applies.
4. Proof of Lemma 3.3
The proof establishes Lemma 3.3 by showing that successive vertex classes contain many rich, disjoint out-sections with exponentially high probability, then iterating this structure across Q_1 through Q_10.
- Setup: The proof fixes J and Q_1,...,Q_10 and reduces the lemma to showing that the relevant event fails with probability o(1).There are at most 2^11n^2n^0.91 choices for these fixed sets.
- Establishing richness: Chernoff’s inequality shows that most vertices of Q_1 have degree near d and that many vertices of B have exactly one neighbor in Q_1.In particular, P[X < 0.9|Q_1|d] ≤ e^−δn.
- Establishing richness: Consequently, with probability at least 1−e^−βn, at least half the vertices in Q_1 and Q_2 have at least d/2 private neighbors.The argument conditions on the previously exposed neighborhood and preserves a sufficiently large remainder B_2.
- Iterating the construction: For each consecutive pair of classes, an auxiliary bipartite graph is random with independently occurring edges whose probability is p_i = 1−(1−p_1)^⌈d_{i−1}/C_i⌉.The first auxiliary graph has p_1 = 1−(1−p)^⌊d/2⌋; applying the partial-cover lemma yields many rich out-sections.
5. Concluding remarks
The paper’s concluding remark extends the counterexample beyond the original conjecture: for every g, the same probabilistic construction yields graphs of girth g that are not normal.
- Concluding remarks: For every g, setting p := n^−1+1/10g and mimicking the proof produces graphs of girth g that are not normal.This extends the paper’s stated goal of disproving the normal graph conjecture.