ProbXiv
sign in

Geometric variants of Hall's Theorem through Sperner's Lemma

Combinatorics · math.CO · posed by Leonardo Martinez, Luis Montejano · open

1 attempt · 1 machine check

Statement

Does there exist a Hall function for the pairwise disjointness relation of the sets of a given family F?

Context

Candidate 4 of the open problems stated in "Geometric variants of Hall's Theorem through Sperner's Lemma", 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: A Hall function for pairwise disjointness would be a finite-valued function h:N→Nh:\mathbb N\to\mathbb N such that for every family F\mathscr F of sets and every finite list of finite subfamilies A1,…,Am⊆F\mathscr A_1,\dots,\mathscr A_m\subseteq\mathscr F, if

    ν(⋃i∈IAi)≥h(∣I∣)\nu\Bigl(\bigcup_{i\in I}\mathscr A_i\Bigr)\ge h(|I|)

    for every nonempty I⊆[m]I\subseteq[m], where ν\nu is the maximum size of a pairwise disjoint subfamily, then one can choose Ai∈AiA_i\in\mathscr A_i so that A1,…,AmA_1,\dots,A_m are pairwise disjoint. This is the natural reconstruction from the paper’s “rainbow set” Hall-type language.

    Result: No such Hall function exists, even for one fixed infinite family of sets.

    Let

    U={(n,i,j):n≥1, 1≤i,j≤n}.U=\{(n,i,j): n\ge1,\ 1\le i,j\le n\}.

    For each nn, define “rows” and “columns”

    Rn,i={(n,i,j):1≤j≤n},Cn,j={(n,i,j):1≤i≤n}.R_{n,i}=\{(n,i,j):1\le j\le n\},\qquad C_{n,j}=\{(n,i,j):1\le i\le n\}.

    Let

    F={Rn,i,Cn,j:n≥1, 1≤i,j≤n}.\mathscr F=\{R_{n,i},C_{n,j}:n\ge1,\ 1\le i,j\le n\}.

    Suppose hh were a Hall function for F\mathscr F. Choose n≥max⁡{h(1),h(2)}n\ge \max\{h(1),h(2)\}. Set

    A1={Rn,1,…,Rn,n},A2={Cn,1,…,Cn,n}.\mathscr A_1=\{R_{n,1},\dots,R_{n,n}\},\qquad \mathscr A_2=\{C_{n,1},\dots,C_{n,n}\}.

    The rows are pairwise disjoint, so ν(A1)=n≥h(1)\nu(\mathscr A_1)=n\ge h(1). The columns are pairwise disjoint, so ν(A2)=n≥h(1)\nu(\mathscr A_2)=n\ge h(1). Also

    ν(A1∪A2)=n≥h(2),\nu(\mathscr A_1\cup\mathscr A_2)=n\ge h(2),

    because all rows form a disjoint subfamily of size nn, while no matching can mix a row and a column since

    Rn,i∩Cn,j={(n,i,j)}≠∅.R_{n,i}\cap C_{n,j}=\{(n,i,j)\}\neq\varnothing.

    Thus all Hall inequalities hold for m=2m=2.

    But there is no disjoint rainbow choice: every possible choice Rn,i∈A1R_{n,i}\in\mathscr A_1 and Cn,j∈A2C_{n,j}\in\mathscr A_2 intersects. Contradiction.

    Therefore the proposed Hall function does not exist.

    Citation: No external theorem is used. The construction is an elementary counterexample to Problem 1.4 of Martinez–Montejano, “Geometric variants of Hall’s Theorem through Sperner’s Lemma,” Electronic Notes in Discrete Mathematics 44 (2013), 127–132.

    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 counterexample attacks the stated Hall-function condition for pairwise disjointness. For any candidate finite-valued hh, choosing n≥max⁡(h(1),h(2))n\ge \max(h(1),h(2)) and taking the two color classes to be the nn rows and nn columns gives

      ν(A1)≥h(1),ν(A2)≥h(1),ν(A1∪A2)≥h(2),\nu(\mathscr A_1)\ge h(1),\quad \nu(\mathscr A_2)\ge h(1),\quad \nu(\mathscr A_1\cup\mathscr A_2)\ge h(2),

      indeed ν(A1∪A2)=n\nu(\mathscr A_1\cup\mathscr A_2)=n. But every row intersects every column, so no disjoint rainbow choice exists. Thus no Hall function exists for this fixed family. I found no existing stronger/same published resolution in the available search.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is a very short two-color row/column obstruction. Even if not explicitly recorded, it is a routine counterexample to any rank-free Hall-type condition for disjoint representatives, and is not substantial enough for a standalone paper.

      Literature check: I found the original Martinez–Montejano Problem 1.4 and only closely related work, notably Aharoni–Haxell-type Hall theorems for bounded-rank hypergraphs and Dumitrescu–Jiang’s “systems of distant representatives,” which cites the original paper. I did not find an explicit published negative answer to this exact fixed-family Hall-function question. The related literature reinforces that bounded-rank hypotheses are essential, but does not appear to publish this particular fixed infinite row/column counterexample.

      Citation: Problem source: Leonardo Martinez and Luis Montejano, “Geometric variants of Hall’s Theorem through Sperner’s Lemma,” Electronic Notes in Discrete Mathematics 44 (2013), 127–132, Problem 1.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.