ProbXiv
sign in

Non-intersecting Ryser hypergraphs

Combinatorics · math.CO · posed by Anurag Bishnoi, Valentina Pepe · open

1 attempt · 1 machine check

Statement

In an intersecting rr-partite hypergraph, what is the smallest size of a vertex cover that does not contain any edge or side?

Context

Candidate 4 of the open problems stated in "Non-intersecting Ryser hypergraphs", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstruct the question as asking for a universal bound, depending only on rr, on

    τnt(H)=min⁡{∣C∣:C is a vertex cover containing no edge and no side}\tau_{\mathrm{nt}}(\mathcal H)=\min\{|C|:C\text{ is a vertex cover containing no edge and no side}\}

    for finite intersecting rr-partite hypergraphs. This is supported by the paper’s phrase “a general upper bound.”

    Result: No such finite bound exists for the stated class.

    For fixed r≥3r\ge 3 and n≥3n\ge 3, let the sides be

    X1={x1},…,Xr−2={xr−2},A={a1,…,an},B={b1,…,bn}.X_1=\{x_1\},\dots,X_{r-2}=\{x_{r-2}\},\quad A=\{a_1,\dots,a_n\},\quad B=\{b_1,\dots,b_n\}.

    Define edges, indices modulo nn, by

    Ei={x1,…,xr−2,ai,bi},Fi={x1,…,xr−2,ai+1,bi}.E_i=\{x_1,\dots,x_{r-2},a_i,b_i\},\qquad F_i=\{x_1,\dots,x_{r-2},a_{i+1},b_i\}.

    All edges contain x1,…,xr−2x_1,\dots,x_{r-2}, so the hypergraph is intersecting.

    Any nontrivial cover cannot contain any xjx_j, since XjX_j is a side. Hence such covers are exactly vertex covers of the cycle C2nC_{2n} on A∪BA\cup B with edges aibia_i b_i and ai+1bia_{i+1}b_i, avoiding the whole sides AA and BB.

    The minimum vertex covers of C2nC_{2n} have size nn, and the only ones of size nn are precisely AA and BB. Thus every allowed cover has size at least n+1n+1. Conversely,

    (A∖{a1})∪{b1,bn}(A\setminus\{a_1\})\cup\{b_1,b_n\}

    has size n+1n+1, covers all edges, contains neither side AA nor BB, and contains no hyperedge because it omits all xjx_j. Therefore

    τnt(H)=n+1.\tau_{\mathrm{nt}}(\mathcal H)=n+1.

    Since nn is arbitrary, the desired “smallest size” is unbounded even for fixed r≥3r\ge 3.

    The literal question can also be undefined: a one-edge rr-partite hypergraph with singleton sides has no cover avoiding both edges and sides.

    Citation: No prior resolution used. Source problem: Bishnoi–Pepe, Non-intersecting Ryser hypergraphs, arXiv:1809.06931.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The construction is mathematically valid for the stated class. For fixed r≥3r\ge3, the hypergraph is finite, rr-partite, rr-uniform, and intersecting. Any allowed cover must omit the singleton sides, so it reduces exactly to a vertex cover of the even cycle on A∪BA\cup B, while avoiding the two whole sides A,BA,B. The only minimum vertex covers of C2nC_{2n} are AA and BB, so the smallest allowed cover has size n+1n+1, as exhibited. Since nn is arbitrary, no bound depending only on rr exists under the stated formulation.

      Novelty assessment

      TYPE1

      Classification rationale: Genuinely new as far as I could determine, but very minor. The counterexample exploits singleton sides shared by all edges, reducing the problem immediately to vertex covers in an even cycle. It answers only the literal broad formulation and would not support a standalone paper; at most it is a short observation/comment on the posed problem.

      Literature check: I found no prior source stating this unboundedness result or an equivalent resolution of Bishnoi–Pepe Problem 2. Exact-phrase searches on arXiv for the problem wording and related phrases returned only the original paper or no results. Searches of related Ryser-hypergraph literature and open web/GitHub results did not reveal a solution. No stronger published statement was located.

      Citation: Source problem: Anurag Bishnoi and Valentina Pepe, “Non-intersecting Ryser hypergraphs,” arXiv:1809.06931, Section 4, Problem 2. No prior resolving citation found.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.