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.