we-solve (beta)

Math-2505 · mathematics · Graph theory

Bounded-Diameter Monochromatic Covers

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
For every integer $r\geq2$, does there exist $D(r)$ such that every $r$-edge-colored complete graph can be covered by $r-1$ monochromatic connected subgraphs, each of diameter at most $D(r)$?

Formulation references: [S1], [S2].

Short English statement

For every integer $r\geq2$, does there exist $D(r)$ such that every $r$-edge-colored complete graph can be covered by $r-1$ monochromatic connected subgraphs, each of diameter at most $D(r)$?

Sources

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

Math-2505-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2505

Ryser obstruction at extension-field ranks: The tree-cover corollary gives complete edge-colored graphs requiring r monochromatic connected components, so r-1 connected subgraphs cannot cover them even without the recorded diameter bound.

Balanced Ryser counterexamples: The tree-cover corollary gives complete edge-colored graphs requiring r monochromatic connected components, so r-1 connected subgraphs cannot cover them even without the recorded diameter bound.

The claimed counterexample lies within the question’s hypotheses and contradicts its universal conclusion.

Bounded-Diameter Monochromatic Covers

OpenAI's claim

Ryser obstruction at extension-field ranks: The first manuscript claims intersecting $r$-partite, $r$-uniform hypergraphs with covering number $r$ at ranks $r=s^n+1$ in the specified large-prime and odd-degree range; a single such example contradicts Ryser’s proposed intersecting-case bound.

Balanced Ryser counterexamples: For each sufficiently large prime $q$, the companion paper claims a uniform hypergraph of rank $q+1$, also with $q+1$ parts, whose edges intersect pairwise and whose covering number is $q+1$; each part has exactly $q+1$ vertices that lie in an edge.

Mathematical statement of the claimed result

Mathematical claim 1.
There is $s_0$ such that for every prime $s\ge s_0$ with $s\equiv2\pmod3$, all sufficiently large odd $n$ yield $q=s^n$ and a finite intersecting $(q+1)$-partite $(q+1)$-uniform hypergraph $H$ with $\tau(H)=q+1$. Intersecting means every two edges meet; $\tau$ is the smallest vertex-set size meeting every edge. Hence $\nu(H)=1$ and $\tau(H)>q\nu(H)$. The same parameters give an $(q+1)$-edge-colored complete graph requiring exactly $q+1$ monochromatic trees to cover its vertices, also when trees are replaced by connected monochromatic subgraphs.
Mathematical claim 2.
For every sufficiently large prime $q$, the paper claims an intersecting $(q+1)$-partite $(q+1)$-uniform hypergraph with parts $V_i$ satisfying \[|V_i|=q+1\ (1\le i\le q+1),\qquad\tau(H)=q+1.\] Every vertex belongs to an edge. Since the matching number is $1$, this refutes $\tau\le(r-1)\nu$ at $r=q+1$. Its complete-graph corollary supplies a $(q+1)$-edge-coloring requiring exactly $q+1$ monochromatic trees, or connected monochromatic subgraphs, for a vertex cover.

Outline of the argument

Ryser obstruction at extension-field ranks: Affine-plane points define ordinary edges, and modified exceptional edges are added to defeat small covers. Incidence savings force any near-minimal ordinary cover to resemble a pencil of lines. Random deletions preserve the required intersections while the exceptional labels make every candidate pencil cover too expensive.

Balanced Ryser counterexamples: Tuples of constituent lines provide many candidates for exceptional edges, with conflicts tracked by a graph. Conditional selection retains compatible candidates while controlling degrees, codegrees, and local prescription probabilities. Pencil-concentration estimates rule out small covers, and a deterministic reduction turns a successful finite line configuration into the balanced hypergraph.

Formal verification

Family 162 describes Lean coverage for the intersecting hypergraph covering obstructions, including the balanced prime-order construction.

Ryser obstruction at extension-field ranks: The manuscript links BalancedRyser.lean, RyserCovering.lean (declaration OAI.RyserCoveringCounterexample.exists_prime_eventually_counterexampleRank), RyserOddExtensions.lean (declaration OAI.RyserOdd.eventualOddFailures_and_infinite).

The documented selection does not cover the entire manuscript assertion relevant here.

Balanced Ryser counterexamples: The manuscript links BalancedRyser.lean, RyserCovering.lean (declaration OAI.RyserCoveringCounterexample.exists_prime_eventually_counterexampleRank), RyserOddExtensions.lean (declaration OAI.RyserOdd.eventualOddFailures_and_infinite).

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →