we-solve (beta)

Math-624 · mathematics · Graph theory

Ryser's Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

An $r$-uniform hypergraph has edges of size $r$ and is $r$-partite when its vertex set splits into $r$ classes with one vertex of each edge in each class. The matching number $\nu(H)$ is the largest number of pairwise disjoint edges, and the cover number $\tau(H)$ is the smallest number of vertices meeting every edge. The target is $\tau(H)\leq(r-1)\nu(H)$ for $r\geq2$. [S1] [S2]

Statement recorded in the supplied source.
For r-partite r-uniform hypergraphs, is the vertex cover number at most (r-1) times the matching number? [S1]
Residual task reported by the archive.

The embedded review (2026-08-17) records: Resolve tau(H)

\ensuremath{≤}
(r-1)nu(H) for r
\ensuremath{≥}
4, beginning with r=4. [S1]

Short English statement

In an r-partite uniform hypergraph, can all edges always be hit using at most r minus one times the size of a largest matching?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 3

Math-624-A3 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-624

Ryser obstruction at extension-field ranks: An intersecting r-partite r-uniform example has matching number one and cover number r, contradicting tau<=(r-1)nu even without any balance restriction.

Balanced Ryser counterexamples: An intersecting r-partite r-uniform example has matching number one and cover number r, contradicting tau<=(r-1)nu even without any balance restriction.

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

Ryser's conjecture

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 includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

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 includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

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 →

Math-624-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-624

Ryser obstruction at extension-field ranks: An intersecting r-partite r-uniform example has matching number one and cover number r, contradicting tau<=(r-1)nu even without any balance restriction.

Balanced Ryser counterexamples: An intersecting r-partite r-uniform example has matching number one and cover number r, contradicting tau<=(r-1)nu even without any balance restriction.

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

Ryser's Conjecture

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 includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

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 includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

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 →

Math-624-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-624

Ryser’s Covering Conjecture for Partite Hypergraphs

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

An $r$-uniform hypergraph has edges of size $r$ and is $r$-partite when its vertex set splits into $r$ classes with one vertex of each edge in each class. The matching number $\nu(H)$ is the largest number of pairwise disjoint edges, and the cover number $\tau(H)$ is the smallest number of vertices meeting every edge. The target is $\tau(H)\leq(r-1)\nu(H)$ for $r\geq2$. [S1] [S2]

Statement recorded in the supplied source.
For r-partite r-uniform hypergraphs, is the vertex cover number at most $r-1$ times the matching number? [S1]
Residual task reported by the archive.

The embedded review $2026-08-17$ records: Resolve tau(H)

\ensuremath{≤}
$r-1$nu(H) for r
\ensuremath{≥}
4, beginning with r=4. [S1]

Short English statement

In an r-partite uniform hypergraph, can all edges always be hit using at most r minus one times the size of a largest matching?

Research attempt

Status and target.
This is an unresolved attempt at the full inequality $\tau(H)\leq(r-1)\nu(H)$. Empty hypergraphs have both parameters zero. For nonempty hypergraphs, the work below proves the elementary $r\nu$ bound, gives a full proof for $r=2$, and constructs sharp examples for $r=q+1$ with $q$ a prime power. These are baseline results, not a new resolution. The archive's residual instruction to start with $r=4$ needs a qualification: White's September 2026 preprint reports a proof of the case $r=4$, $\nu=2$. This attempt records that specific external claim and does not certify its computer-assisted checks or extend it to arbitrary matching number. https://arxiv.org/abs/2609.14281
A cover from a maximum matching.
Let $M$ be a maximum matching. Its union is a cover: otherwise an edge disjoint from every member of $M$ could be added. Since matching edges are disjoint, this proves $\tau\leq r\nu$. For an $r$-partite hypergraph, each entire vertex class is also a cover, so \[ \nu\leq\tau\leq\min\{r\nu,|V_1|,\ldots,|V_r|\}. \] The lower bound follows because a vertex can hit at most one edge of a matching. In particular, any counterexample must have more than $(r-1)\nu$ vertices in every part after isolated vertices are removed. This is a necessary size restriction, not a contradiction.
The bipartite case by alternating paths.
For $r=2$, write the parts $L,R$. From unmatched vertices of $L$, traverse nonmatching edges from $L$ to $R$ and matching edges from $R$ to $L$. Let $Z_L,Z_R$ be the reached vertices. No unmatched vertex of $R$ is reached, since the resulting alternating path would augment $M$. The set $C=(L\setminus Z_L)\cup Z_R$ covers every edge. Indeed, an uncovered edge would run from $Z_L$ to $R\setminus Z_R$. If it is not in $M$, the traversal reaches its right endpoint; if it is in $M$, its left endpoint was reached through its matched right endpoint. Both possibilities contradict its being uncovered.

For each matched edge, either both endpoints are reached or neither is: reachability of the right endpoint implies reachability of its matched left endpoint, and a reached matched left endpoint was reached through the right endpoint. Exactly one endpoint of every matched edge therefore lies in $C$. Unmatched left vertices lie in $Z_L$, and unmatched right vertices lie outside $Z_R$. Thus $|C|=|M|$, proving $\tau=\nu$ and Ryser's bound for $r=2$. The use of a path that alternates two types of edges is the step for which an arbitrary uniform hypergraph supplies no immediate analogue.

Sharpness via affine lines.
Let $q$ be a prime power and work over $\mathbb F_q$. Make a vertex for each affine line in the plane $\mathbb F_q^2$. Partition these vertices into the $q+1$ parallel classes: the vertical lines, and the lines $y=ax+b$ for each slope $a\in\mathbb F_q$. For each point $(x,y)$, make one hyperedge consisting of the $q+1$ lines through that point. Each edge meets each parallel class once, so the hypergraph is $(q+1)$-partite and $(q+1)$-uniform. Two distinct points lie on a common line, hence their hyperedges intersect, and $\nu=1$.

A vertex cover of this hypergraph is precisely a set of affine lines covering all $q^2$ points. Each line contains $q$ points, so fewer than $q$ lines cannot cover the plane, even if all of their points were distinct. The $q$ lines of any one parallel class do cover the plane. Consequently $\tau=q=r-1$. Taking $m$ disjoint copies gives $\nu=m$ and $\tau=(r-1)m$: matching and cover numbers add across components. This is the familiar dual-affine-plane sharpness mechanism; the finite-field construction above proves the asserted parameters without assuming the conjecture. For general orders not admitting the required field, it asserts no construction.

Why deleting a class from the matching cover fails.
A tempting plan is to keep the vertices of $M$ in only $r-1$ parts. Already for $r=3$, take edges \[ (a_1,b_1,c_1),\quad(a_2,b_2,c_2),\quad(a_3,b_3,c_1). \] The first two form a maximum matching of size two: the first and third intersect, so all three cannot form a matching. Deleting the third part from their union leaves the third edge uncovered. The example does satisfy Ryser's conjecture; its purpose is to refute this fixed deletion rule. A successful replacement must choose vertices using the other edges, as alternating reachability did in the bipartite case.
Verification and remaining step.
The companion exact check constructs the affine-line hypergraphs for $q=2,3,5$ and verifies the partite condition, pairwise intersection, and cover number by exhaustive subsets of line vertices. These finite checks test the construction, while the argument above handles every prime power. No search over all partite hypergraphs is claimed. For $r\geq4$ and arbitrary matching number, the missing step is a cover-selection or exchange theorem saving $\nu$ vertices from the elementary $r\nu$ bound. Neither the sharp examples nor the bipartite algorithm establishes that theorem. Status: unresolved.

Sources

  • Additional source A Patrick White, Tuza's Ryser-conjecture claim for four-partite hypergraphs with matching number two, preprint, 2026. Abstract and scope checked 2026-10-01. https://arxiv.org/abs/2609.14281.
  • Additional source B Ahmad Abu-Khazneh and Alexey Pokrovskiy, Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs, 2014. Background on extremal examples; the affine construction used here is proved in the attempt. https://arxiv.org/abs/1409.4938.

  • S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1440 (GRAPH-053), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

  • S2 Ron Aharoni, Ryser's conjecture for tripartite 3-graphs, Combinatorica 21 $2001$, 1–4. https://doi.org/10.1007/s004930170001. Bibliographic information from the supplied record.

  • S3 Penny E. Haxell and Alex Scott, On Ryser's conjecture, Electronic Journal of Combinatorics 19 $2012$, P23. https://doi.org/10.37236/1175. Bibliographic information from the supplied record.

  • S4 Ryser's conjecture, Graph-theory open problems tracker, reviewed 2026-05-08. https://mlelarge.github.io/graph-conjectures/op/rysers_conjecture/. Bibliographic information from the supplied record.

Go to contribution →