ProbXiv
sign in

On the co-degree threshold for the Fano plane

Combinatorics · math.CO · posed by Louis DeBiasio, Tao Jiang · open

1 attempt · 1 machine check

Statement

What is lim sup⁡n→∞{e(G)(nr):G⊆([n]r),Gcontainsnosubgraphthatcoverspairs}?\limsup_{n \to\infty}\left\{\frac{e(G)}{\binom{n}{r}}:G \subseteq\left(\begin{array}{c}{[n]}\\{r}\end{array}\right),G \text{containsnosubgraphthatcoverspairs}\right\}?

Context

Candidate 4 of the open problems stated in "On the co-degree threshold for the Fano plane", 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: For a fixed integer r≥2r\ge 2, let an rr-uniform hypergraph HH “cover pairs” mean

    ∣V(H)∣≥r+1andδ2(H)≥1,|V(H)|\ge r+1\quad\text{and}\quad \delta_2(H)\ge 1,

    i.e. every pair of vertices of HH lies in some edge of HH. The reconstructed problem is to determine

    Lr=lim sup⁡n→∞{e(G)(nr):G⊆([n]r),  G contains no subhypergraph that covers pairs}.L_r=\limsup_{n\to\infty}\left\{\frac{e(G)}{\binom nr}:G\subseteq \binom{[n]}r,\;G\text{ contains no subhypergraph that covers pairs}\right\}.

    The condition ∣V(H)∣≥r+1|V(H)|\ge r+1 is part of the paper’s definition; without it every single edge would trivially cover all pairs among its rr vertices.

    Result:

    Lr=r!rr.\boxed{L_r=\frac{r!}{r^r}}.

    Proof. Let GG be an rr-graph with no pair-covering subgraph. Define its Lagrangian

    λ(G)=max⁡xv≥0∑vxv=1∑e∈E(G)∏v∈exv.\lambda(G)=\max_{\substack{x_v\ge 0\\ \sum_v x_v=1}} \sum_{e\in E(G)}\prod_{v\in e}x_v.

    Choose an optimal weighting with support S={v:xv>0}S=\{v:x_v>0\} minimal.

    If u,v∈Su,v\in S are not contained together in any edge lying wholly inside SS, then, with all other weights fixed and xu+xvx_u+x_v fixed, the Lagrangian is linear in xu,xvx_u,x_v. Hence moving all weight from one of u,vu,v to the other does not decrease the value, contradicting minimality of ∣S∣|S|. Therefore every pair in SS is contained in some edge inside SS.

    Thus G[S]G[S] covers pairs unless ∣S∣≤r|S|\le r. Since GG has no pair-covering subgraph, ∣S∣≤r|S|\le r. Hence

    λ(G)≤max⁡x1,…,xr≥0∑xi=1x1⋯xr=1rr.\lambda(G)\le \max_{\substack{x_1,\dots,x_r\ge0\\ \sum x_i=1}} x_1\cdots x_r =\frac1{r^r}.

    For an nn-vertex GG, the uniform weighting gives

    e(G)nr≤λ(G)≤1rr,\frac{e(G)}{n^r}\le \lambda(G)\le \frac1{r^r},

    so

    e(G)(nr)≤nrrr(nr)→r!rr.\frac{e(G)}{\binom nr}\le \frac{n^r}{r^r\binom nr}\to \frac{r!}{r^r}.

    Thus Lr≤r!/rrL_r\le r!/r^r.

    For the lower bound, partition [n][n] as evenly as possible into rr parts V1,…,VrV_1,\dots,V_r, and take all rr-edges meeting each part in exactly one vertex. This complete rr-partite rr-graph has

    e(G)=∏i=1r∣Vi∣=(1+o(1))(n/r)r,e(G)=\prod_{i=1}^r |V_i|=(1+o(1))(n/r)^r,

    so its density tends to r!/rrr!/r^r. It contains no pair-covering subgraph: any r+1r+1 vertices include two vertices in the same part, and no edge contains such a pair.

    Therefore Lr=r!/rrL_r=r!/r^r.

    Verification audit: the proof uses exactly the paper’s definition of “covers pairs”; no finiteness beyond finite nn-vertex hypergraphs is added; the lower construction avoids all pair-covering subgraphs, not only induced ones; and the upper bound applies to every admissible GG, giving the required limsup.

    Citation: No prior exact citation is needed for the resolution above; the proof is self-contained, using the standard hypergraph Lagrangian merging argument.

    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 proof attacks the correct extremal-density statement and is complete. The minimal-support Lagrangian argument correctly forces the support to be pair-covered; since such subgraphs are forbidden, the support has size at most rr, giving λ(G)≤1/rr\lambda(G)\le 1/r^r and hence the upper bound. The balanced complete rr-partite construction gives the matching lower bound and indeed contains no pair-covering subgraph.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely not explicitly recorded, but it is a very minor consequence of standard hypergraph Lagrangian machinery. The key lemma—an optimal minimal-support Lagrangian subgraph covers pairs—is routine and widely used. Once observed, the upper bound is immediate, and the balanced complete rr-partite rr-graph gives the matching lower bound. This is not substantial enough for a standalone paper beyond perhaps a short remark answering DeBiasio–Jiang’s Problem 4.

      Literature check: I found no exact prior statement giving

      lim sup⁡e(G)(nr)=r!rr\limsup \frac{e(G)}{\binom nr}= \frac{r!}{r^r}

      for hypergraphs with no pair-covering subgraph. Searches for the exact problem wording, “covers pairs” with “Problem 4”, DeBiasio/Jiang, “r!/r^r”, “pair-covered/2-covered hypergraph”, and related Turán-density phrases did not reveal a published solution.

      However, the proof is essentially the standard Lagrangian dense-subgraph reduction: dense Lagrangian subgraphs cover pairs, and any hypergraph has a Lagrangian-preserving dense subgraph. This standard fact is stated, for example, in Peng–Yan, Fact 2.5 and Remark 2.7, and goes back to Frankl–Rödl-type Lagrangian arguments.

      Citation: Relevant standard source: Yuejian Peng and Zilong Yan, “Lagrangian densities of hypergraph cycles,” arXiv:1810.13077, Fact 2.5 and Remark 2.7. Original problem: Louis DeBiasio and Tao Jiang, “On the co-degree threshold for the Fano plane,” arXiv:1204.1927, Problem 4.

      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.