← All problems

The edge-pattern convex-combination conjecture

7 years old · traced to

Let PP be a dd-regular edge-rooted pattern of depth rr and girth 2r+22r+2. For each edge-rooted pattern, let e(P)\mathbf{e}(P) denote its constraint vector, and let Tr′(d)\mathcal{T}'_r(d) be the specified family of dd-regular edge-rooted trees of depth rr. The constraint e(P)\mathbf{e}(P) is weaker than a convex combination of constraints from this family in the sense that there exist T1,…,Tm∈Tr′(d)T_1,\dots,T_m\in\mathcal{T}'_r(d) and λ1,…,λm∈[0,1]\lambda_1,\dots,\lambda_m\in[0,1] with

∑i=1mλi=1\sum_{i=1}^m\lambda_i=1

and, for every α∈(Q+)r+1\bm{\alpha}\in{\left(\mathbb{Q}^+\right)}^{r+1},

α ⁣⊤(∑i=1mλie(Ti))≥1  ⟹  α ⁣⊤e(P)≥1.\bm{\alpha}^{\!\top}\left(\sum_{i=1}^m\lambda_i\mathbf{e}(T_i)\right)\ge 1\quad\implies\quad\bm{\alpha}^{\!\top}\mathbf{e}(P)\ge 1.

This would explain why the bounds obtained from edge-rooted trees remain valid at girth 2r+22r+2, and would generalize the cases checked for r=2r=2 and d∈{3,4}d\in\{3,4\}.

References
  1. François Pirot and Jean-Sébastien Sereni, “Fractional chromatic number, maximum degree and girth”, arXiv:1904.05618 (2021).

Progress summary

Refreshed
Open · progress reported

A reader-submitted calculation claims the conjecture fails in one small case, but no independent verification was found.

Pirot and Sereni's conjecture, recorded in their 2019 work, asks whether every eligible edge-rooted pattern is dominated by a convex combination of the specified tree constraints. The catalogue records no resolution in that source.

Community submission (unverified), November 7, 2026

A submitted argument claims a counterexample at d=3d=3 and r=2r=2: an 88-vertex pattern allegedly has e(P)=(2/5,14/5,4/5)\mathbf{e}(P)=(2/5,14/5,4/5) and, for α=(1/1000,7/27,1/3)\bm{\alpha}=(1/1000,7/27,1/3), satisfies α ⁣⊤e(P)=67027/67500<1\bm{\alpha}^{\!\top}\mathbf{e}(P)=67027/67500<1, whereas every relevant tree satisfies α ⁣⊤e(T)≥3001/3000\bm{\alpha}^{\!\top}\mathbf{e}(T)\ge 3001/3000. If correct, this refutes the conjecture in that case; the submission is unverified.

Current status (as of November 2026): The conjecture has no independently verified resolution; an unverified submission claims it is false for d=3d=3 and r=2r=2.

Sources

Solutions 1

A cubic counterexample to edge-pattern convex dominationSee full solutionHide full solution

Result and scope. Pirot-Sereni (arXiv:1904.05618; SIAM J. Discrete Math. 35(4) (2021) 2815-2843) Conjecture 2, also Conjecture 1.5.1 of Pirot's 2019 thesis, is false at d = 3, r = 2. The 8-vertex edge-rooted pattern P (root edge 01; edges 01,02,03,15,17,34,46,56: a 6-cycle with two pendants) is 3-regular, of exact depth 2 and girth 6, with e(P) = (2/5,14/5,4/5). With alpha = (1/1000,7/27,1/3), alpha.e(P) = 67027/67500 < 1, while every acyclic 3-regular depth-2 edge-rooted pattern (all 81 leaf-count forms) has alpha.e(T) >= 3001/3000. So no convex combination of tree constraints is weaker than e(P). The source's optimized bounds (Lemma 10) are unaffected.

Complete proof: A cubic counterexample to edge-pattern convex domination · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.