Counterexamples to Conforti's Subtree Conjecture for Mixed-Integer Bipartite Covers

For a bipartite graph G = (U ∪ V, E), a set I ⊆ U ∪ V and rationals b_ij, let S(G,I) = {x ∈ R^(U∪V) : x_i + x_j ≥ b_ij (ij ∈ E), x_i ∈ Z (i ∈ I)}, and let k be the least positive integer with kb integral. In the 2008 Oberwolfach report on combinatorial optimization, Conforti conjectured that conv S(G,I) is the intersection of the hulls conv S(T, I ∩ V(T)) over the subtrees T of G whose integral vertices are exactly their leaves. This would place the membership problem for conv S(G,I) in coNP. He noted that the case k = 2 follows from work of Conforti, Gerards and Zambelli, and that the conjecture was open for every k ≥ 3. We show that it fails for every k ≥ 3. For each such k we give two unicyclic counterexamples. One has six vertices. The other has seven, and in it every integral vertex is a pendant vertex with a continuous neighbour, so the standard normalisation of such sets (splitting integral vertices) does not remove it. In both, an explicit point lies in conv S(T, I ∩ V(T)) for every subtree T of G, but violates a facet-defining inequality of conv S(G,I) by (k − 2)/(2k − 3). The proofs are short and by hand. We also describe exact validity certificates based on an extended formulation, and use them to certify a further normalised counterexample for k = 3. The complexity of the membership problem remains open. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: OWR-2489-004 and OWR-2489-009 (ulamai/UnsolvedMath; Oberwolfach Report 51/2008, Conforti's Conjecture 2 on mixed-integer bipartite covers).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-30
DOI
https://doi.org/10.5281/zenodo.23062397
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Counterexamples to Conforti's Subtree Conjecture for Mixed-Integer Bipartite Covers

Alper Ferudun
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Counterexamples to Conforti's Subtree Conjecture for Mixed-Integer Bipartite Covers

Alper Ferudun
preprint en

Abstract

For a bipartite graph G = (U ∪ V, E), a set I ⊆ U ∪ V and rationals b_ij, let S(G,I) = {x ∈ R^(U∪V) : x_i + x_j ≥ b_ij (ij ∈ E), x_i ∈ Z (i ∈ I)}, and let k be the least positive integer with kb integral. In the 2008 Oberwolfach report on combinatorial optimization, Conforti conjectured that conv S(G,I) is the intersection of the hulls conv S(T, I ∩ V(T)) over the subtrees T of G whose integral vertices are exactly their leaves. This would place the membership problem for conv S(G,I) in coNP. He noted that the case k = 2 follows from work of Conforti, Gerards and Zambelli, and that the conjecture was open for every k ≥ 3. We show that it fails for every k ≥ 3. For each such k we give two unicyclic counterexamples. One has six vertices. The other has seven, and in it every integral vertex is a pendant vertex with a continuous neighbour, so the standard normalisation of such sets (splitting integral vertices) does not remove it. In both, an explicit point lies in conv S(T, I ∩ V(T)) for every subtree T of G, but violates a facet-defining inequality of conv S(G,I) by (k − 2)/(2k − 3). The proofs are short and by hand. We also describe exact validity certificates based on an extended formulation, and use them to certify a further normalised counterexample for k = 3. The complexity of the membership problem remains open. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: OWR-2489-004 and OWR-2489-009 (ulamai/UnsolvedMath; Oberwolfach Report 51/2008, Conforti's Conjecture 2 on mixed-integer bipartite covers).

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Counterexamples to Conforti's Subtree Conjecture for Mixed-Integer Bipartite Covers — Alper Ferudun · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS