Canonical-augmentation backtracking search for Erdős–Gyárfás minimal counterexamples (P13-free)

Statement

What the paper actually proves, and how (corrected framing). arXiv:2410.22842 (Hegde, Sandeep, Shashank, IIT Dharwad; v2 2025-02-11) proves two theorems, both entirely by computer search — there is no hand-written hole-length case analysis anywhere in this paper (that style of argument belongs only to the earlier Gao–Shan $P_8$ paper [arXiv:2109.01277] and Hu–Shen $P_{10}$ paper [arXiv:2308.05675], which this paper explicitly credits as inspiration: *"Inspired by a case analysis in [Gao–Shan], we prove with the aid of a computer search that the conjecture is true for $P_{13}$-free graphs"*):

- Theorem 0.1: every $P_{13}$-free graph with $\delta(G)\ge3$ has a cycle of length a power of 2 (the full, unrestricted Erdős–Gyárfás conclusion). - Theorem 0.2: every $P_{12}$-free graph with $\delta(G)\ge3$ has a cycle of length 4 or 8 specifically (the sharper Gao–Shan/Hu–Shen-style conclusion) — proved with a *separate, modified* implementation ('4-8-cycles' branch) that only forbids cycles of length 4 and 8 rather than all powers of 2, which is a strictly smaller search (hence $P_{12}$, one notch below $P_{13}$, is tractable with this narrower target).

Both theorems reduce, via one shared lemma, to running a single backtracking function explore(G, k) on a seed graph and checking it returns True.

Facts

- The reduction to a single seed run (Lemma 1 + Corollary 1). Let $G^*$ be a *minimal counterexample* to Erdős–Gyárfás (i.e. no proper induced subgraph of $G^*$ is itself a counterexample) that is $P_k$-free for the *smallest* $k$ such that this holds — equivalently $G^*$ has an induced $P_{k-1}$. Lemma 1 proves by induction (on $n^*-n$, the gap between $|V(G^*)|$ and a partial vertex set) that if explore is run on any graph $G$ on vertices $\{v_0,\dots,v_{n-1}\}$ that agrees with $G^*$ on all edges among $\{v_0,\dots,v_{n-2}\}$ and on $v_{n-1}$'s already-known neighbors, explore(G,k) must return False. Corollary 1 specializes this to the smallest possible partial graph: the seed path $G=v_0v_1\cdots v_{k-1}$ (i.e. exactly $P_k$, or rather the induced $P_{k-1}$ found inside $G^*$ extended one vertex). So: *if a $P_k$-free minimal counterexample exists, explore on the seed path of length $k$ must return False.* Contrapositive: if explore returns True for every $k$ from 3 to $t$, no $P_t$-free minimal counterexample exists for any minimality-witnessing $k\le t$, and by induction down to the trivial base case ($P_2$-free graphs have no edges at all, so trivially no counterexample), every $P_t$-free min-degree-3 graph has a power-of-2 cycle. - The search states: partial graphs grown one vertex at a time by canonical augmentation, not a symmetry-reduced isomorph-free enumeration. explore(G,k) (Figure 1, transcribed verbatim below) operates on a graph $G$ with a *fixed, totally ordered* vertex sequence $v_0,\dots,v_{n-1}$, where by construction $v_0,\dots,v_{n-2}$ already have degree $\ge3$ and $v_{n-1}$ is the newest vertex, possibly still degree-deficient. - Branching rule. For each subset $S\subseteq\{v_0,\dots,v_{n-2}\}$ that is a "set of potential safe neighbors of $v_{n-1}$" — meaning: none of $S$'s pairs $\{v_i,v_{n-1}\}$ is already an edge, and adding all of them simultaneously creates no "forbidden cycle" (a cycle whose length is a power of 2, or for the P12/Theorem-0.2 variant, specifically length 4 or 8) — the algorithm adds those edges and recurses. - Pruning rule 1 (induced-$P_k$ check). After adding $S$'s edges, if the resulting graph contains an induced $P_k$, that branch is abandoned (continue) — this is what makes the search a search over *$P_k$-free* graphs specifically. - Pruning rule 2 (forbidden-cycle check, baked into "safe neighbor" membership). A candidate edge set is never even considered if it would create a power-of-2-length cycle (or a 4-/8-cycle for Theorem 0.2) — this is what makes "the graph has no power-of-2 cycle" an *invariant maintained by construction* rather than checked after the fact. - Growth/anchor rule. If the branch survives both prunes, call get_largest_low_degree_vertex(G): the highest-index vertex with degree $<3$. If none exists (anchor_node == -1) — i.e. $G$ now has $\delta(G)\ge3$, is $P_k$-free, and has no forbidden cycle — **this is the win/termination condition, and it is a *contradiction*, not a success: the algorithm has just constructed an actual finite counterexample to the theorem being tested, so `explore` returns `False` immediately. Otherwise, a fresh vertex $v_n$ is added adjacent to `anchor_node` only (forcing progress toward min-degree-3 for that specific vertex) and `explore` recurses on the enlarged graph; if the recursive call returns `False`, that `False` propagates all the way up (short-circuit). After trying all sets $S$ without finding a `False`, the function returns `True` — meaning every way of completing this partial graph is provably blocked before it can become a full counterexample. - Exact pseudocode (Figure 1, transcribed from the HTML source, arxiv.org/html/2410.22842v2): ``` function explore(G, k): # V(G) = {v_0,...,v_{n-1}} for each set S of potential safe neighbors of v_{n-1}: add edge {v_i, v_{n-1}} to G, for each v_i in S if there is an induced P_k in G: continue anchor_node <- get_largest_low_degree_vertex(G) if anchor_node == -1: return False # G is a counterexample add node v_n and edge {v_n, anchor_node} to G if not explore(G, k): return False remove node v_n from G remove edge {v_i, v_{n-1}} from G, for each v_i in S return True ``` `get_largest_low_degree_vertex` returns the largest-index vertex of degree $<3$, or $-1$ if $\delta(G)\ge3$ already. - What is run, per theorem. Theorem 0.1 ($P_{13}$): `explore(G,k)` run with $G=$ the path $v_0v_1\cdots v_{k-1}$, for every $k$ from 3 to 13; every run returned `True`. Theorem 0.2 ($P_{12}$, sharper 4-or-8 conclusion): a separate implementation ('4-8-cycles' branch of the repo) with the forbidden-cycle set restricted to $\{4,8\}$, run up to $k=12$. - Runtime (Table 1, server: 2.6 GHz CPU, 72 cores). C++ serial: $k\le9$: <0.2s; $k{=}10$: 2s; $k{=}11$: 32s; $k{=}12$: 31m32s; $k{=}13$: 11h56m. Cilk parallel (72 cores): $k\le9$: <0.05s; $k{=}10$: 0.1s; $k{=}11$: 1.4s; $k{=}12$: 29s; $k{=}13$: 17m17s. Theorem 0.2 ($P_{12}$, restricted 4/8 target): serial 1m39s for $k=11$, 3h9m for $k=12$. - Why it stops at $k=13$: memory, not a structural obstruction.** Direct quote: *"The parallel execution was terminated due to out of memory error when ran for $k=14$."* No serial $k=14$ time is reported at all (implying it was not completed either, or deemed infeasible given the $k=12\to13$ growth: serial time roughly ×23 per step, so $k=14$ would be on the order of days-to-weeks serially even before considering memory). The paper does not identify any structural/combinatorial obstruction at $P_{14}$ — the blowup is presented purely as a computational-resource (time+memory) wall in the current implementation, not evidence the statement becomes false or unprovable by this method at $P_{14}$. - The paper's own closing question is exactly "how far does this go" — and it is left explicitly open, no ceiling conjectured. Verbatim: *"We end with the following question: Is Algorithm 1 capable of resolving the conjecture for $P_k$-free graphs for every integer $k\ge14$? In other words, is there an infinite graph with minimum degree at least 3 neither having an induced $P_k$ nor having a cycle of length a power of 2?"* — i.e. they frame the open question as: does an *infinite* $P_k$-free, min-degree-3, power-of-2-cycle-free graph exist for some $k$ (which would make explore never terminate / return True vacuously without ever reaching $-1$-anchor termination for a finite witness), not as a bound on how large $k$ their specific hardware can reach. No numeric ceiling (P14, P16, P18, etc.) is conjectured anywhere in the paper. - The method provably does NOT generalize past paths. Verbatim: *"The technique that we used is not helpful for proving the conjecture for $H$-free graphs when $H$ is not a path."* Two constructions given: (a) if $H$ contains a cycle, an infinite min-degree-3 tree is $H$-free and power-of-2-cycle-free, so explore would run forever without terminating; (b) if $H$ is a non-path tree, replacing every vertex of an infinite cubic tree with a triangle (each triangle-vertex adjacent to exactly one vertex of a neighboring triangle) gives a claw-free infinite graph where every induced tree is automatically a path, hence $H$-free for any non-path tree $H$, again with explore never terminating. This is a real, stated structural limit of the method — but it limits the *object class* (paths only), not the *value of $k$* within the path family. - Independent check that the search logic is sound: it reconstructs the known Markström graph exactly. The paper's own correctness-testing appendix (test 4, verbatim): *"We obtained all the four cubic graphs with minimum number (24) of vertices (found by Markström) having no 4-cycle and no 8-cycle but having a 16-cycle by guiding the execution with proper values of $k$ and by restricting the degree to be 3. Only one of them, known as Markström graph, is planar. It is $P_{18}$-free but has an induced $P_{17}$."* This is the same 24-vertex Markström construction — a cubic $C_4$-and-$C_8$-free graph with a $C_{16}$, $P_{18}$-free with an induced $P_{17}$ — that our own project uses as the explicit $\le P_{17}$ ceiling witness on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle. This paper is fully aware of it (cites Markström 2002 [10] directly, uses it as ground truth to validate explore's correctness) but does not treat it as a conjectured ceiling for the "cycle 4-or-8" sharpened line — Markström's graph rules out "4-or-8" for anything $P_{18}$-or-weaker (it has neither $C_4$ nor $C_8$ but is not $P_{17}$-free), consistent with, but not asserted as tight for, the paper's own $P_{12}$ result. The paper draws no explicit connection between this test-4 fact and a conjectured stopping point for Theorem 0.2's line. - Code is public, real, and runnable. GitHub: github.com/rbsandeep/Erdos-Gyarfas (cited as ref [7] in the paper: *"Verifier for Erdős–Gyárfás conjecture on $P_k$-free graphs, October 2024"*), C++ (93.7%) + Makefile, MIT-licensed, with CITATION.cff. Branches confirmed via direct WebFetch of the repo: main (serial), cilk (parallel, per Blumofe et al.'s Cilk runtime [1995]), 4-8-cycles (restricted-target variant used for Theorem 0.2), logs (manual verification traces for $3\le k\le5$), tests (unit tests for internal functions), special-graphs (the Markström-graph reconstruction of test 4). Build: make clean && make; run: ./out/a.out <k>. Authors state they welcome scrutiny — the appendix's whole purpose is inviting exactly this kind of reproduction/extension attempt.

Technique

How to extend this to $P_{14}$ (the concrete, actionable recipe, per the paper's own algorithm + repo):

1. Clone github.com/rbsandeep/Erdos-Gyarfas, cilk branch (fastest: 17m17s at $k=13$ vs 11h56m serial — a ~41× speedup from 72-core parallelism, suggesting the wall at $k=14$ is Cilk's per-task memory overhead multiplied across many more concurrent recursion branches, not raw compute). 2. The stated failure mode is out-of-memory, not timeout — so the highest-leverage change is *not* more cores/time but reducing memory footprint per recursion branch: (a) run the main (serial, low-memory) branch at $k=14$ with a long time budget instead of Cilk, accepting the ~day-plus runtime extrapolated from the ×23 per-step growth ($11\text{h}56\text{m}\times23\approx11$ days serial guess, very rough since branching factor is graph-size- and $k$-dependent, not fixed); or (b) reduce Cilk's task-parallel granularity / add explicit isomorph-rejection or symmetry-breaking (the algorithm as described does not appear to canonically deduplicate isomorphic partial graphs across different $S$-branches — every subset $S$ of potential safe neighbors is explored independently even if two different $S$ choices lead to isomorphic graphs), which is the standard lever (nauty-style canonical form pruning, see nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families)) for cutting a backtracking search's memory/branching by orders of magnitude without weakening correctness. 3. Alternatively, target Theorem-0.2's narrower "4-or-8" restricted-cycle variant (the 4-8-cycles branch) one notch further, i.e. attempt $P_{13}$-free $\Rightarrow$ cycle 4-or-8 (one step past their $P_{12}$ result) before attempting the harder general-power-of-2 $P_{14}$ target — the paper's own data shows the restricted variant is meaningfully cheaper (3h9m at $k=12$ vs 11h56m serial for the general target at $k=13$), so this is the lower-hanging extension. 4. Any successful extension is directly checkable against the paper's own correctness protocol (appendix tests 1-4): cross-check against Hu–Shen's $P_{10}$ result, manual log inspection for small $k$, unit tests, and Markström-graph reconstruction — all four are concrete, reusable regression tests already in the repo.

WHEN this class of method applies. Any "$\delta(G)\ge d\Rightarrow$ forced substructure" statement restricted to an $H$-free class where $H$ is a *path* specifically — per the paper's own explicit negative result, the anchor-vertex-forces-min-degree canonical-growth trick relies on $H$ being a path (so that "no induced $P_k$ yet" is monotone-checkable incrementally as vertices are added one at a time along a single growing chain); it provably fails to terminate for cycle-containing or non-path-tree $H$.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the general (unrestricted) Erdős–Gyárfás conjecture; this page's method is the current computational frontier of the $P_t$-free restricted-class attack line on it, and the source of the $\le P_{17}$-ceiling Markström-graph fact this page cross-references. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — the $P_8$ (Gao–Shan, hand case analysis) and $P_{10}$ (Hu–Shen, hand case analysis) predecessor results that this paper's explore search is "inspired by" and directly extends; that page's provenance note should be read alongside this one since it pre-dates this page's direct primary-source verification of the $P_{12}$/$P_{13}$ split (P12 is not hand-proved in 2410.22842, contrary to what a shallow read might suggest — both P12 and P13 are pure computer search, just against two different forbidden-cycle target sets). - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — the general proof schema (assume minimal violator, derive constraints, contradict) this page's Lemma 1/Corollary 1 instantiate; here the "constraint" is entirely delegated to exhaustive machine search rather than hand-derived local rules. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — the natural next lever for extending past $P_{13}$: canonical-form/isomorph-rejection pruning, which this paper's explore does not appear to use (every branch over subsets $S$ is explored independently with no stated symmetry-breaking), and which is the standard fix for backtracking search space blowup of exactly this shape. - SAT/CP-SAT-based finite counterexample search and verification — sibling finite-counterexample-search paradigm; a SAT/CP-SAT re-encoding of the same "does a $P_k$-free, min-degree-3, no-power-of-2-cycle graph exist below size $N$" question could plausibly benefit from CDCL clause-learning across branches in a way this paper's plain backtracking (no learning, no isomorph-rejection) does not — a concrete alternative avenue to try at $P_{14}$ if pruning the existing C++ search doesn't clear the memory wall.

REPO DEEP-SCAN (2026-07-03) — cosa contiene davvero il loro GitHub

Scansione completa di TUTTI i branch di github.com/rbsandeep/Erdos-Gyarfas (non solo il paper — errore di processo: prima avevamo letto solo l'arXiv):

- main/cilk/4-8-cycles: il codice della ricerca (sequenziale + Cilk). - `special-graphs`: contiene GIÀ i testimoni del tetto — 3× 24-node-cubic-no-4-8-cycles-p18-free.{1,2,3}.txt, un 28-node-cubic-no-4-8-cycles-p21-free.txt, markstroem.txt, graph_test.py (verifica isomorfismo/cicli), capture-log. README: "24-node cubic P18-free graphs that do not have 4 to 8 cycles but contain 16 cycles". → il "tetto P₁₇" è loro prior art. - tests: unit test (json.hpp). logs: plotting. - NESSUN P14 in nessun branch. L'unico "14" è una macro C++ in json.hpp. Il paper dichiara che a k=14 la versione parallela va OOM.

Conseguenza operativa

l'unico contributo potenzialmente nuovo è la dimostrazione esaustiva P14 (nostro k=14), che aggira il loro OOM con la parallelizzazione a sottoalberi. Tutto il resto (bound n≤19 a parte) è già in mano loro.

Lezione di processo

quando costruiamo su un paper con codice, scansionare TUTTI i branch del repo e metterli nel wiki PRIMA di dichiarare novità. Un "risultato mondiale" era in un branch pubblico.