gpt 6 astra ultra attempt on Math-454

Erdős Matching Conjecture

Definitions and mathematical statement

Let $n,k,s$ be positive integers with $n\ge ks$, and let $\mathcal F\subseteq\binom{[n]}k$. Its matching number is the maximum number of pairwise disjoint members. If this number is at most $s-1$, the conjecture asserts \[ |\mathcal F|\le \max\left\{\binom{ks-1}{k}, \binom nk-\binom{n-s+1}{k}\right\}. \] The first candidate is realized by all $k$-subsets of a fixed $(ks-1)$-element set. The second is realized by all $k$-subsets meeting a fixed $(s-1)$-element set. Each family avoids $s$ disjoint members, explaining both terms and the parameter convention. Formulations using matching number at most $s$ replace this entry's $s$ by $s+1$; mixing those conventions changes the formula.

Formulation and concept references: [S1].

Short English statement

How large can a uniform family of sets be when it contains no s pairwise disjoint members? The conjecture gives two competing sharp constructions.

Research attempt

Scope and source check (27 September 2026).

Throughout, the forbidden matching has $s$ members, so the allowed matching number is $s-1$. The source [S1] uses a different parameter for the allowed matching number; its parameter is $q=s-1$ here. Its checked 2026 version proves a large-parameter result for four-uniform families in a range beginning at $n\geq5q$, subject to its sufficiently-large condition. That result does not by itself cover every $n\geq4s$ required in the four-uniform instance of this entry, still less all uniformities.

This attempt gives complete proofs of the endpoint $n=ks$, the case $s=2$, and an explicit, deliberately nonoptimal large-$n$ range. It proves the shifting lemma used in one of those arguments and tests a class of competing constructions. These are classical elementary mechanisms reconstructed here, not claims of new best bounds. The general intermediate range remains open in this attempt.

Write \[ A(n,k,s)=\binom{ks-1}{k},\qquad B(n,k,s)=\binom nk-\binom{n-s+1}{k}. \] The first is independent of $n$ once $n\geq ks$, but the notation keeps all parameters visible. We use $\binom ab=0$ if $0\leq a<b$.

Extremal constructions and boundary cases.

All $k$-sets inside a fixed $(ks-1)$-set have no $s$ disjoint members, since those would require $ks$ different elements. All $k$-sets meeting a fixed $(s-1)$-set also avoid an $s$-matching: disjoint members would need different points of that set. Their sizes are respectively $A$ and $B$. These checks establish lower bounds on the extremal size, not the desired upper bound for an arbitrary family.

When $s=1$, the matching restriction forces the family to be empty, and both expressions are zero. When $k=1$, the matching number equals the number of members, and both expressions equal $s-1$. Henceforth assume $k,s\geq2$ unless explicitly stated otherwise.

Proposition 450.1: an exact proof at $n=ks$.

Choose a uniformly random ordering of $[n]$ and divide it into $s$ successive blocks of size $k$. These blocks are disjoint, so at most $s-1$ belong to $\mathcal F$. Each block is individually a uniform $k$-set. Taking expectations gives \[ s\frac{|\mathcal F|}{\binom{ks}{k}}\leq s-1. \] Thus \begin{equation}\label{wsref-0-61-34-35-30-3a-65-6e-64-70-6f-69-6e-74} |\mathcal F|\leq\frac{s-1}{s}\binom{ks}{k} =\binom{ks-1}{k}=A(ks,k,s). \end{equation} The second extremal construction is among the families to which this inequality applies, so its size is also at most $A$ at this endpoint. This proves the exact maximum prescribed by the conjecture when $n=ks$.

More generally, divide a random ordering into $q=\lfloor n/k\rfloor$ full $k$-blocks, discarding a remainder of fewer than $k$ points. The same argument proves \begin{equation}\label{wsref-0-61-34-35-30-3a-70-61-72-74-69-74-69-6f-6e} |\mathcal F|\leq\frac{s-1}{q}\binom nk. \end{equation} It is a valid uniform inequality whenever $q\geq s$, but it generally falls short of the two-construction maximum away from the endpoint. Keeping the floor and its dependence on $n$ is necessary; treating $q$ as $s$ for all $n$ would lose still more information.

The immediate cover bound and its limitation.

Take a maximal matching of size $r\leq s-1$, and let $U$ be the union of its members. Every edge meets $U$, or it could be added to the matching. Since $|U|=kr\leq k(s-1)$, \begin{equation}\label{wsref-0-61-34-35-30-3a-63-6f-76-65-72} |\mathcal F|\leq\binom nk-\binom{n-k(s-1)}k. \end{equation} For fixed $k,s$ and large $n$, this has leading term $k(s-1)\binom{n-1}{k-1}$, whereas $B$ has leading term $(s-1)\binom{n-1}{k-1}$. The factor $k$ is an actual weakness of this argument.

It cannot be removed simply by asserting that every family with matching number $s-1$ has a cover of size $s-1$. The complete $k$-uniform family on $ks-1$ vertices has minimum cover size $(ks-1)-k+1=k(s-1)$: a smaller cover leaves at least $k$ uncovered support vertices and hence an uncovered member, while a cover of that size leaves only $k-1$. Thus the two extremal constructions reflect different structures. The existence of a small matching does not force the star-type structure.

Lemma 450.2: shifting does not increase matching number.

For $i<j$, define $S_{ij}$ on a family by replacing a member $E$ containing $j$ and not $i$ with $E-j+i$ if the latter is not already in the family; otherwise keep $E$. This preserves cardinality. It also satisfies \begin{equation}\label{wsref-0-61-34-35-30-3a-73-68-69-66-74} \nu(S_{ij}\mathcal F)\leq\nu(\mathcal F). \end{equation} To prove this, take a matching in the shifted family. Every new member contains $i$, so at most one member of that matching is new. If there is none, the matching already belongs to $\mathcal F$. Otherwise let its new member be $E$, whose original preimage $E-i+j$ lies in $\mathcal F$.

If no other member contains $j$, replace $E$ by its preimage, preserving disjointness. If another member $H$ contains $j$, then it does not contain $i$, and it survived the shift. Therefore $H-j+i$ was already in $\mathcal F$; otherwise $H$ would have been replaced. Replace the two members by \[ E-i+j,\qquad H-j+i. \] They are in the original family, remain disjoint from one another, and remain disjoint from every unchanged member. This reconstructs a matching of the same size in $\mathcal F$ and proves (a450:shift).

Repeatedly applying any shift that changes the family terminates: the integer sum of all labels over all its members strictly decreases. The resulting family is fully shifted, with the same cardinality and no larger matching number. This legitimizes reduction to shifted families, but does not by itself prove an extremal classification.

Proposition 450.3: a complete proof for $s=2$.

Here $\mathcal F$ is intersecting. We prove for $n\geq2k$ that \begin{equation}\label{wsref-0-61-34-35-30-3a-65-6b-72} |\mathcal F|\leq\binom{n-1}{k-1}. \end{equation} For $k=1$ there is at most one member. At $n=2k$, the $k$-sets occur in complementary disjoint pairs; an intersecting family takes at most one from each pair. This gives $\tfrac12\binom{2k}k=\binom{2k-1}{k-1}$.

For $n>2k$, shift the family and split it into $\mathcal B$, the $k$-sets not containing $n$, and $\mathcal A$, the $(k-1)$-sets obtained by removing $n$ from the other members. The family $\mathcal B$ is intersecting. So is $\mathcal A$: if $A_1,A_2\in\mathcal A$ were disjoint, choose a point $r\in[n-1]\setminus(A_1\cup A_2)$, possible since their union has size $2k-2<n-1$. The shifted property makes $A_1\cup\{r\}$ a member of $\mathcal F$. It is disjoint from $A_2\cup\{n\}$, a contradiction.

Strong induction on $n$, covering all admissible $k$ at each smaller ground-set size, now gives \[ |\mathcal F|=|\mathcal B|+|\mathcal A| \leq\binom{n-2}{k-1}+\binom{n-2}{k-2} =\binom{n-1}{k-1}. \] The hypotheses for both induction calls hold: $n-1\geq2k$ and $n-1\geq2(k-1)$. This proves (a450:ekr). It equals $B(n,k,2)$ and is at least $A(n,k,2)$, since the two coincide at $n=2k$ and $B$ increases with $n$. Hence it proves the exact conjectured bound for every $s=2$ instance.

The proof uses a feature special to forbidding two disjoint members: the link at $n$ remains intersecting. A general link with matching restriction $s-1$ does not automatically have matching restriction $s-2$, so copying this induction for arbitrary $s$ would assume the main missing structural step.

Proposition 450.4: an explicit elementary large-$n$ range.

For $k,s\geq2$, define \[ N(k,s)=2k^2(k-1)(s-1)+1. \] If $n\geq N(k,s)$ and $\nu(\mathcal F)\leq s-1$, then \begin{equation}\label{wsref-0-61-34-35-30-3a-6c-61-72-67-65-6e} |\mathcal F|\leq B(n,k,s). \end{equation} In particular the conjecture holds in this range. We prove the estimate by induction on $s$, using the empty-family case $s=1$ as the initial step.

Let $d(v)$ be the number of members containing $v$, and put \[ T=k(s-1)\binom{n-2}{k-2}. \] First suppose some vertex $v$ has $d(v)>T$. If the family avoiding $v$ contained $s-1$ disjoint members, their union $U$ would have $k(s-1)$ points. At most \[ |U|\binom{n-2}{k-2}=T \] members through $v$ could meet $U$, by assigning any such member one of its points in $U$ and using a union bound. A member through $v$ outside this collection would complete an $s$-matching. This is impossible. Thus the family avoiding $v$ has matching number at most $s-2$.

For $s\geq3$, $n-1\geq N(k,s-1)$, so induction applies to that family; for $s=2$ it is empty directly. Adding at most $\binom{n-1}{k-1}$ members through $v$ gives \[ |\mathcal F|\leq \binom{n-1}{k}-\binom{n-s+1}{k} +\binom{n-1}{k-1}=B(n,k,s). \] This completes the high-degree case.

If instead every degree is at most $T$, the maximal-matching cover $U$ from (a450:cover) yields \begin{equation}\label{wsref-0-61-34-35-30-3a-6c-6f-77-64-65-67-72-65-65} |\mathcal F|\leq\sum_{v\in U}d(v) \leq k^2(s-1)^2\binom{n-2}{k-2}. \end{equation} On the other hand telescoping Pascal's identity gives \[ B(n,k,s)=\sum_{j=0}^{s-2}\binom{n-j-1}{k-1} \geq(s-1)\binom{n-s+1}{k-1}. \] The ratio of this last binomial coefficient to $\binom{n-1}{k-1}$ is \[ \prod_{r=0}^{k-2}\left(1-\frac{s-2}{n-1-r}\right) \geq1-\frac{(k-1)(s-2)}{n-k+1}\geq\frac12. \] The first inequality is the elementary product bound $\prod(1-u_r)\geq1-\sum u_r$ for $0\leq u_r\leq1$. The last follows from the stated lower bound on $n$; that bound also makes every factor nonnegative. Therefore \[ B(n,k,s)\geq\frac{s-1}{2}\binom{n-1}{k-1} =\frac{(s-1)(n-1)}{2(k-1)}\binom{n-2}{k-2} \geq k^2(s-1)^2\binom{n-2}{k-2}. \] This dominates (a450:lowdegree) and finishes the induction.

The proof intentionally uses coarse estimates. It is useful because every constant and parameter is explicit, and it demonstrates how a high-degree reduction and a low-degree cover estimate can cooperate. It leaves the substantial range $ks<n<N(k,s)$ untouched except for the special cases already proved. It is not presented as improving the sharper literature.

Testing intermediate construction types.

For $1\leq i\leq k$, consider the classical families \[ \mathcal F_i=\{E\in\tbinom{[n]}k:\ |E\cap[is-1]|\geq i\}. \] They have no $s$ disjoint members, because those would require at least $is$ distinct points from a set of size $is-1$. Their exact sizes are \begin{equation}\label{wsref-0-61-34-35-30-3a-69-6e-74-65-72-6d-65-64-69-61-74-65} |\mathcal F_i|=\sum_{j=i}^k \binom{is-1}{j}\binom{n-is+1}{k-j}. \end{equation} The endpoints $i=1$ and $i=k$ are the two proposed extremal constructions. It is reasonable to test whether intermediate indices give a larger family for some parameters, but a negative computational search would only exclude those tested cases and that particular construction scheme. It would not classify arbitrary shifted families.

Exact checks and unresolved step.

The diagnostic evaluates (a450:intermediate) for $2\leq k\leq6$, all $s\geq2$ with $ks\leq n\leq50$, and all $i$. In this finite grid every size is at most $\max\{A,B\}$. It also enumerates all simple graphs on at most six vertices, computes their matching numbers exactly, and checks the two-uniform conjectured bound wherever $n\geq2s$. On all graphs on six vertices and all three-uniform families on five vertices it directly verifies that every elementary shift preserves cardinality and does not increase the matching number. The latter check concerns the general lemma; it does not pretend that five vertices satisfy the six-vertex threshold for a three-uniform two-matching problem.

These finite checks audit the formulas and the shifting implementation. The proofs of the endpoint, intersecting case, and explicit large-$n$ theorem are independent of enumeration. What remains is a sharp structural or counting argument for general families in the intermediate range, capable of distinguishing clique-like concentration from a small-cover configuration without losing the factor $k$ in (a450:cover). No such argument is established here. The full Erdős matching conjecture in the selected parameter convention remains unresolved in this attempt.

UNRESOLVED. The partial results above do not establish the full selected statement.

Sources

• S1 Frankl, Lu, Ma and Wu, Towards the Erdős matching conjecture for 4-uniform hypergraphs, Conjecture1.1; substitute q=s-1 in their matching-number convention. https://arxiv.org/pdf/2602.19230. Formulation source.