Complement-graph symmetry argument — linking two graph parameters via G and its complement Ḡ

Statement

Given a graph $G=(V,E)$ on vertex set $V$, its complement $\bar G$ has the same vertex set and edge set $\binom V2\setminus E$ (an edge exists in $\bar G$ exactly where it is *absent* in $G$). The complement-graph symmetry argument is the family of proof techniques that compare a graph invariant, or two different graph invariants, evaluated on $G$ and on $\bar G$ simultaneously, exploiting two logically separate facts that are easy to conflate but must both be checked before the technique applies:

1. Deterministic complement-invariance of one parameter. Some graph parameters are literally unchanged by complementation: $A(G)=A(\bar G)$ for *every* graph $G$, not just in expectation or whp. Examples: the cochromatic number $\zeta(G)=\zeta(\bar G)$ (a homogeneous partition of $V(G)$ into cliques and independent sets is, verbatim, a homogeneous partition of $V(\bar G)$ into independent sets and cliques — complementation just swaps which parts are which type, so the minimum number of parts is unchanged); the clique–independence duality $\omega(G)=\alpha(\bar G)$ (a clique in $G$ is exactly an independent set in $\bar G$); Ramsey symmetry $R(s,t)=R(t,s)$ (swap the two colour classes of a red/blue edge-colouring of $K_n$, which is the same as complementing the red graph); and Lovász's Perfect Graph Theorem, "$G$ is perfect $\iff \bar G$ is perfect" (Lovász 1972). 2. A second parameter that is monotone (increasing or decreasing) in the edge set, so that its value on $\bar G$ is controlled — via a correlation inequality or an extremal bound — by its value on $G$. Chromatic number $\chi(G)$ is the canonical example: adding an edge can never decrease $\chi$, so $\chi$ is an increasing function of $E(G)$; consequently $\chi(\bar G)$, viewed as a function of the *same* underlying edge-indicator variables of $G$, is a decreasing function of them (adding an edge to $G$ removes a potential edge from $\bar G$).

Combining (1) and (2) on a single graph $G$ (deterministic setting) or a single random graph draw (probabilistic setting) links the two evaluations without needing to reason about $G$ and $\bar G$ as if they were independent objects.

Deterministic (extremal) form — Nordhaus–Gaddum theorem. For every graph $G$ on $n$ vertices, $$2\sqrt n \;\le\; \chi(G)+\chi(\bar G) \;\le\; n+1, \qquad n \;\le\; \chi(G)\cdot\chi(\bar G) \;\le\; \left(\frac{n+1}{2}\right)^{\!2}.$$ (E. A. Nordhaus, J. W. Gaddum, "On complementary graphs," *Amer. Math. Monthly* 63(3) (1956) 175–177.) The upper bound on the sum is proved by an induction on $n$ using the fact that some vertex has degree $\ge (n-1)/2$ in $G$ or in $\bar G$; equality graphs are characterized (Finck) and called NG-graphs.

Probabilistic form — self-complementary distribution of $G(n,1/2)$, plus Harris/FKG. If $G\sim G(n,1/2)$ (each of the $\binom n2$ potential edges present independently with probability $1/2$), then $\bar G \sim G(n,1/2)$ too — flipping "present" and "absent" is a measure-preserving bijection on $\{0,1\}^{\binom n2}$ under the uniform/product-$1/2$ measure. So $G$ and $\bar G$ have *identical marginal law*, even though they are perfectly (anti-)correlated as a pair. This is the engine behind the modern (2024) resolution machinery for Erdős–Gimbel's cochromatic-number problems (see Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?, Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988), Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G)):

> Proposition (Heckel, arXiv:2408.13839, Prop. 3). If $g(n)$ is such that $\mathbb P(\chi(G)-\zeta(G)\le g(n))>0.999$ for $G\sim G_{n,1/2}$, then $\chi(G_{n,1/2})$ is concentrated on some interval $[s_n,t_n]$ of length $g(n)$ with probability $>0.9$.

*Proof mechanism, in full (fetched directly from the paper, arxiv.org/html/2408.13839v2):* let $\mathcal D=\{\chi(G)\le s_n\}$ where $s_n$ is the smallest integer with $\mathbb P(\chi(G)\le s_n)\ge 0.05$ — a decreasing event in the edge-indicator coordinates of $G$. Let $\mathcal U=\{\chi(\bar G)\le s_n+g(n)\}$ — as a function of the *same* coordinates, $\chi(\bar G)$ is decreasing in $\bar G$'s edges hence increasing in $G$'s edges, so $\mathcal U$ is an increasing event. Because $\zeta(\bar G)=\zeta(G)$ (fact 1 above) and $\bar G\sim G_{n,1/2}$ (self-complementary distribution), the hypothesis $\mathbb P(\chi-\zeta\le g(n))>0.999$ transfers verbatim to $\bar G$: $\mathbb P(\chi(\bar G)-\zeta(G)\le g(n))>0.999$ too. A union bound over $\mathcal D$ (probability $\ge 0.05$ by construction, using $\zeta(G)\le\chi(G)\le s_n$ typically) and this transferred bound gives $\mathbb P(\mathcal U\cap\mathcal D)\ge 1-0.001$. Now Harris's Lemma — for a decreasing event $\mathcal D$ and increasing event $\mathcal U$ on a product measure, $\mathbb P(\mathcal U\cap\mathcal D)\le\mathbb P(\mathcal U)\,\mathbb P(\mathcal D)$ (negative correlation of oppositely-monotone events, see Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation)) — is rearranged to $\mathbb P(\mathcal U)\ge \mathbb P(\mathcal U\cap\mathcal D)/\mathbb P(\mathcal D) \ge (1-0.001)/0.05 \to$ (quoted verbatim) $\ge 1-0.001/0.05=0.98$. So with probability $\ge0.98$, $\chi(\bar G)\le s_n+g(n)$; combined with $\chi(G)$ concentrating near $s_n$ by the same logic applied to $G$ itself, both $\chi(G)$ and $\chi(\bar G)$ — two identically-distributed but oppositely-monotone copies of $\chi(G_{n,1/2})$ evaluated on the same random object — are forced into an interval of length $g(n)$ with high probability. This is exactly a non-concentration statement about $\chi(G_{n,1/2})$ itself, so any *known* lower bound on how spread out $\chi(G_{n,1/2})$ must be (Heckel, *JAMS* 2021; Heckel–Riordan, *JLMS* 2023 — see Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou)) becomes a lower bound on $g(n)$, i.e. on how small $\chi(G)-\zeta(G)$ can possibly be forced whp.

Facts

- Origin of the extremal (deterministic) form: E. A. Nordhaus, J. W. Gaddum, "On complementary graphs," *Amer. Math. Monthly* 63(3) (1956) 175–177 — proved $\chi(G)+\chi(\bar G)\le n+1$ and $\chi(G)\chi(\bar G)\le\left(\frac{n+1}2\right)^2$, plus the trivial lower bounds via AM–GM on $\chi(G)\ge n/\alpha(G)$-type counting. Spawned "several hundred" follow-up papers extending the same $G$-vs-$\bar G$ two-sided-bound recipe to dozens of other graph parameters (domination number, independence number, various colouring variants) — see the survey M. A. Aouchiche, P. Hansen, "A survey of Nordhaus–Gaddum type relations," *Discrete Appl. Math.* (2013), sciencedirect.com/science/article/pii/S0166218X11005075. - Clique–independence duality: $\omega(G)=\alpha(\bar G)$ and $\alpha(G)=\omega(\bar G)$ for every graph $G$ — the special case of the deterministic-invariance idea with $A(G)=\omega(G)$, $A(\bar G) := \alpha(G)$ treated as *two different* parameters on the same graph rather than one parameter compared across $G,\bar G$; this duality is what makes $R(s,t)=R(t,s)$ true for Ramsey numbers (complementing a red/blue 2-colouring of $K_n$ swaps which colour has an $s$-clique vs. a $t$-clique). - Lovász's Perfect Graph Theorem (L. Lovász, 1972, *Discrete Math.* 2(3) 253–267): $G$ is a perfect graph iff $\bar G$ is — the deepest classical instance of "a structural graph property is complement-invariant," proved via a direct combinatorial (not probabilistic) complement argument, resolving the Weak Perfect Graph Conjecture. - Cochromatic number is complement-invariant for every graph, not just probabilistically: $\zeta(G)=\zeta(\bar G)$ always. This deterministic fact (true for a single fixed $G$, no randomness needed) is the "anchor" that the whole probabilistic Heckel/Steiner argument for Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? is built on — it is what lets a *whp* statement about $\chi(G)-\zeta(G)$ get "reflected" onto $\bar G$ while $\zeta$ itself stays exactly fixed. - Self-complementary distribution is special to $p=1/2$: for $G(n,p)$ with $p\ne 1/2$, $\bar G\sim G(n,1-p)\ne G(n,p)$, so the "transfer the whp statement to $\bar G$ for free" step fails — this technique is intrinsically tied to the $p=1/2$ (equivalently, uniform-over-all-labelled-graphs) random graph model. It does *not* directly generalize to other edge-probabilities without re-deriving a coupling between $G(n,p)$ and $G(n,1-p)$. - Heckel's paper is a short, sharp corollary application: A. Heckel, "On a question of Erdős and Gimbel on the cochromatic number," arXiv:2408.13839, *Electron. J. Combin.* 31(4):P4.72 (2024) — the *entire* technical content beyond citing known non-concentration results for $\chi(G_{n,1/2})$ is the ~1-page Proposition 3 argument quoted above; it is a template for "if you already have a non-concentration/spread result for parameter $X$, and a complement-invariant parameter $\zeta$ satisfies $\zeta\le X$ pointwise, you get a lower bound on $X-\zeta$ almost for free." - Independent, contemporaneous rediscovery: R. Steiner, "On the difference between the chromatic and cochromatic number," arXiv:2408.02400 (Aug 2024) — found the identical complement/Harris-FKG connection independently within weeks of Heckel; Steiner's Theorem 1.7 gives a companion positive-probability bound $\mathbb P(\chi(G_n)-\zeta(G_n)\ge n^{1/2-\epsilon})\ge c>0$ for infinitely many $n$, via the same $\zeta(\bar G)=\zeta(G)$ + Harris–FKG mechanism, and separately uses a different (non-random, gadget-construction) technique to disprove Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) in the same paper. - **The technique only produces a *lower bound* on the gap $\chi-\zeta$, never an upper bound or exact value**: it converts "$\chi-\zeta$ is small whp" into "$\chi(G_{n,1/2})$ is concentrated," which is then contradicted by an *external* non-concentration input; it supplies no information at all in the direction of proving $\chi-\zeta$ is *bounded*. Fully resolving Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? (does $\chi-\zeta\to\infty$ a.s., for *all* $n$, not just infinitely many or 95% of $n$) remains open as of this wiki's research pass (2026-07-02) — see Heckel's stronger 2025 paper arXiv:2409.17614 for the current record (95% of $n$, via an unrelated second-moment technique, not this complement-symmetry argument). - A companion, structurally distinct use of complementation in the same problem cluster: erdosproblems.com/762 records Steiner's *disproof* of the Erdős–Gimbel–Straight conjecture via a gadget/blow-up construction that does not use the complement-symmetry argument at all — a useful contrast showing complementation-symmetry is one tool among several the same authors reach for on the same problem family, not a universal hammer.

Technique

WHEN it applies: you have (or want to bound) the difference, sum, or product of two graph parameters $A,B$ evaluated on the same graph, where: - $A$ satisfies (or can be shown to satisfy) $A(G)=A(\bar G)$ exactly, for every graph in the class of interest — check this first; it is usually a one-line combinatorial verification (partition-based parameters like $\zeta$, or dual parameters like $\omega/\alpha$, are the most common source), and - $B$ is monotone in the edge set (increasing or decreasing) — again usually immediate from the definition ($\chi$, clique cover number, etc. are increasing; independence number, girth-type parameters are decreasing).

Two regimes: 1. Extremal/deterministic regime (Nordhaus–Gaddum flavor): no randomness at all — you want a bound valid for *every* graph $G$ on $n$ vertices, typically via an explicit induction or degree-counting argument comparing $G$ and $\bar G$ directly (e.g. "some vertex has degree $\ge(n-1)/2$ in $G$ or $\ge(n-1)/2$ in $\bar G$, since the two degrees sum to $n-1$"). 2. Probabilistic/whp regime (Heckel–Steiner flavor): you have a *random* $G\sim G(n,1/2)$ specifically (the $p=1/2$ self-complementary case), and you want a whp lower bound on $B(G)-A(G)$ by contradicting a known non-concentration result for $B$ itself. This regime additionally needs a monotone-events correlation inequality (Harris/FKG, see Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation)) to convert the *conditional* probability bound (obtained via a union bound after transferring the hypothesis to $\bar G$) into an *unconditional* one.

WHY it works (the mechanism): complementation is an *involution* on the edge-indicator space that (a) fixes some parameters exactly (by a purely combinatorial swap-argument, e.g. clique ↔ independent set) while (b) *reversing the monotonicity direction* of others (increasing-in-$G$'s-edges becomes decreasing-in-$G$'s-edges when re-expressed via $\bar G$). At $p=1/2$ this involution is *also measure-preserving*, so it upgrades from "a symmetry of a single graph" to "a symmetry of the whole probability space" — any whp event transfers to its complement-image for free, without needing a separate argument. Layering the Harris/FKG negative-correlation inequality on top (step 2's oppositely-monotone events $\mathcal D,\mathcal U$) is what lets you combine "the transferred event has high *unconditional* probability" with "a fixed decreasing event $\mathcal D$ has controllable probability $\ge0.05$" into a nontrivial *conditional*-probability lower bound on $\mathcal U$ that would not follow from a naive union bound alone (a naive union bound only gives $\mathbb P(\mathcal U)\ge \mathbb P(\mathcal U\cap\mathcal D)-\mathbb P(\mathcal D^c)$, which can be vacuous; dividing through via Harris instead of subtracting is the sharper move that makes the $0.05\to0.98$ arithmetic work).

The reusable recipe: 1. Find your complement-invariant anchor $A$. Check $A(G)=A(\bar G)$ combinatorially (partition-type parameters and clique/independence duals are the standard sources; also check whether $A$ is even *defined* symmetrically, e.g. cochromatic number's definition is manifestly symmetric under swapping "clique part" and "independent-set part" labels). 2. Identify the monotone parameter $B$ you actually care about, and pin down its monotonicity direction in the edge set (increasing/decreasing) explicitly — get this backwards and the whole argument inverts silently. 3. (Deterministic regime) Set up a direct comparison inequality between $B(G)$ and $B(\bar G)$ — often via an extremal/counting argument (a vertex of controlled degree in one of $G,\bar G$; a partition argument; induction on $n$) — to get a Nordhaus–Gaddum-style two-sided bound on $B(G)+B(\bar G)$ or $B(G)\cdot B(\bar G)$, then substitute $A(\bar G)=A(G)$ to relate $B$ and $A$ on the *single* graph $G$. 4. (Probabilistic regime, $p=1/2$) Use $\bar G\sim G(n,1/2)$ (same law as $G$) to transfer any whp statement about $B(G)-A(G)$ to $B(\bar G)-A(G)$ (substituting $A(\bar G)=A(G)$ from step 1) *for free* — this is where the self-complementary distribution does the work, no correlation inequality needed yet. 5. Define the matching monotone events $\mathcal D$ (decreasing, e.g. "$B(G)\le$ threshold") and $\mathcal U$ (increasing, built from the transferred statement about $\bar G$ re-expressed as a function of $G$'s edges) and apply Harris/FKG's negative-correlation inequality $\mathbb P(\mathcal U\cap\mathcal D)\le\mathbb P(\mathcal U)\mathbb P(\mathcal D)$, rearranged to lower-bound $\mathbb P(\mathcal U)$ from a union-bound-derived lower bound on $\mathbb P(\mathcal U\cap\mathcal D)$. 6. Read off a non-concentration statement for $B(G_{n,1/2})$ itself (both $B(G)$ and $B(\bar G)$, identically distributed but coupled oppositely, land in a common short interval), and contradict it using an *externally proved* non-concentration/spread lower bound for $B$ — this final step is the payoff and requires importing a separate, often much harder, result (for $B=\chi$: Heckel *JAMS* 2021 / Heckel–Riordan *JLMS* 2023, see Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou)).

Limitations / what it does NOT give: the technique is a *reduction*, not a self-contained proof — step 6 needs a genuine non-concentration input from elsewhere, so the strength of the final bound on $B-A$ is capped by the strength of the best known non-concentration result for $B$. It gives only a *lower* bound on the gap $B-A$ (evidence the gap is large), never an upper bound. It is intrinsically tied to $p=1/2$ (or more generally to any setting with an exact, measure-preserving, monotonicity-reversing involution on the underlying probability space) — attempting the same recipe at $G(n,p)$, $p\ne1/2$ requires first establishing a substitute coupling between $G(n,p)$ and $G(n,1-p)$, which does not come for free.

Related

- Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — the correlation-inequality machinery (negative correlation of oppositely-monotone events on a product measure) that step 5 of the recipe invokes; this page focuses on the *complementation-specific* setup (which events to build, why they are oppositely monotone, why the base measure is self-complementary) rather than the inequality itself. - Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou) — the external non-concentration results for $\chi(G_{n,1/2})$ (Heckel *JAMS* 2021, Heckel–Riordan *JLMS* 2023) that step 6 imports to turn the complement-symmetry reduction into an actual numeric lower bound on $\chi-\zeta$. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the *other* main technique in this same problem cluster (Heckel's later 95%-of-$n$ result, arXiv:2409.17614, via tame-colouring-profile second-moment machinery rather than the complement-symmetry route); useful contrast showing the two techniques attack the same conjecture from different angles and give incomparable-strength partial results. - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — the open $\$1000$ Erdős–Gimbel problem ($\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ a.s.?) whose best partial results (Heckel arXiv:2408.13839, Steiner arXiv:2408.02400) are direct applications of this exact technique. - Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) — sibling Erdős–Gimbel–Straight problem from the same 1988/1993 paper family, disproved by Steiner in the *same* arXiv:2408.02400 paper, but via an unrelated gadget/blow-up construction, not this complement-symmetry technique — a direct in-corpus contrast of "same authors, same paper, two different tools." - Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G) — a different $\chi$-vs-$\zeta$ problem ("large $\chi$ forces a subgraph with large $\zeta$"), solved by Alon–Krivelevich–Sudakov via a $p=1/2$ random-subgraph + union-bound argument that is thematically related (same $p=1/2$ self-complementary regime, same two parameters $\chi,\zeta$) but does not use the complement-of-the-whole-graph trick — it samples a random *subgraph*, not the complement.