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
- Alper Ferudun
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