Erdős Problem #1020

Erdős Problem 1020 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: falsifiable. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1020.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT. Let $r\ge 3$ and $k\ge 1$ be integers. For each $n\ge r$, let $f(n;r,k)$ be the maximum number of edges in an $r$-uniform hypergraph $\mathcal{H}$ on an $n$-element vertex set such that $\mathcal{H}$ contains no matching of size $k$ (i.e. no $k$ pairwise vertex-disjoint hyperedges). The statement in the problem file asserts that for all $r\ge 3$, \[ (\star)\qquad f(n;r,k)=\max\left(\binom{rk-1}{r},\ \binom{n}{r}-\binom{n-k+1}{r}\right). \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement describes $(\star)$ as the Erdős matching conjecture (open in general for $r\ge 3$) and lists several ranges where it has been proved.

ATTACK PLAN. First check whether $(\star)$, as written for all $n$, is even consistent with the trivial bound $f(n;r,k)\le \binom{n}{r}$. If inconsistent, give an explicit counterexample and then state a minimal corrected version (typically with an assumption like $n\ge rk-1$).

WORK.

Counterexample to the literal statement $(\star)$. Take $(r,k,n)=(3,2,3)$.

Verification of the left-hand side. An $r$-uniform hypergraph on $n=3$ vertices with $r=3$ has exactly one possible edge, namely the full vertex set. In particular, every such hypergraph has at most one edge. Also, a matching of size $k=2$ would require two disjoint $3$-edges, which is impossible on $3$ vertices. Therefore the constraint “no matching of size $2$” is vacuous, and hence \[ f(3;3,2)=\binom{3}{3}=1. \]

Verification of the right-hand side. Compute \[ \binom{rk-1}{r}=\binom{5}{3}=10, \qquad \binom{n}{r}-\binom{n-k+1}{r}=\binom{3}{3}-\binom{2}{3}=1-0=1. \] So the right-hand side of $(\star)$ equals $\max(10,1)=10$.

Conclusion. We have $f(3;3,2)=1\ne 10$, so $(\star)$ is false as a universal identity over all $n$. $\square$

Minimal corrected statement (consistent with the standard conjecture). A natural minimal correction is to restrict to $n\ge rk-1$ (so the first extremal construction “all $r$-sets on $rk-1$ vertices” can actually live inside an $n$-vertex set). One may also explicitly cap by $\binom{n}{r}$: \[ f(n;r,k)=\min\left\{\binom{n}{r},\ \max\left(\binom{rk-1}{r},\ \binom{n}{r}-\binom{n-k+1}{r}\right)\right\}. \] The corrected conjecture remains open in general for $r\ge 3$ (as indicated by the problem statement).

FAST REALITY CHECK. The above counterexample is the smallest possible parameter choice with $r\ge 3$ and $k\ge 2$; it already violates $(\star)$ because $\binom{rk-1}{r}$ can exceed the trivial upper bound $\binom{n}{r}$ when $n<rk-1$.

VERIFICATION. All computations are exact. The only subtle point is the definition of “contains no set of $k$ many independent (i.e. pairwise disjoint) edges”: for $n<rk$ this is indeed vacuous, hence $f(n;r,k)=\binom{n}{r}$. This directly conflicts with $(\star)$ whenever $\binom{rk-1}{r}>\binom{n}{r}$, which occurs for the exhibited parameters.

FINAL. FULL SOLUTION

COUNTEREXAMPLE/DISPROOF. The literal identity $(\star)$ is false for $(r,k,n)=(3,2,3)$, since $f(3;3,2)=1$ while the right-hand side equals $10$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Let $r\ge 3$ and $k\ge 1$ be integers. For each $n\ge r$, let $f(n;r,k)$ be the maximum number of edges in an $r$-uniform hypergraph $\mathcal{H}$ on an $n$-element vertex set such that $\mathcal{H}$ contains no matching of size $k$ (i.e. no $k$ pairwise vertex-disjoint hyperedges). The statement in the problem file asserts that for all $r\ge 3$, \[ (\star)\qquad f(n;r,k)=\max\left(\binom{rk-1}{r},\ \binom{n}{r}-\binom{n-k+1}{r}\right). \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement describes $(\star)$ as the Erdős matching conjecture (open in general for $r\ge 3$) and lists several ranges where it has been proved.

ATTACK PLAN. First check whether $(\star)$, as written for all $n$, is even consistent with the trivial bound $f(n;r,k)\le \binom{n}{r}$. If inconsistent, give an explicit counterexample and then state a minimal corrected version (typically with an assumption like $n\ge rk-1$).

WORK.

Counterexample to the literal statement $(\star)$. Take $(r,k,n)=(3,2,3)$.

Verification of the left-hand side. An $r$-uniform hypergraph on $n=3$ vertices with $r=3$ has exactly one possible edge, namely the full vertex set. In particular, every such hypergraph has at most one edge. Also, a matching of size $k=2$ would require two disjoint $3$-edges, which is impossible on $3$ vertices. Therefore the constraint “no matching of size $2$” is vacuous, and hence \[ f(3;3,2)=\binom{3}{3}=1. \]

Verification of the right-hand side. Compute \[ \binom{rk-1}{r}=\binom{5}{3}=10, \qquad \binom{n}{r}-\binom{n-k+1}{r}=\binom{3}{3}-\binom{2}{3}=1-0=1. \] So the right-hand side of $(\star)$ equals $\max(10,1)=10$.

Conclusion. We have $f(3;3,2)=1\ne 10$, so $(\star)$ is false as a universal identity over all $n$. $\square$

Minimal corrected statement (consistent with the standard conjecture). A natural minimal correction is to restrict to $n\ge rk-1$ (so the first extremal construction “all $r$-sets on $rk-1$ vertices” can actually live inside an $n$-vertex set). One may also explicitly cap by $\binom{n}{r}$: \[ f(n;r,k)=\min\left\{\binom{n}{r},\ \max\left(\binom{rk-1}{r},\ \binom{n}{r}-\binom{n-k+1}{r}\right)\right\}. \] The corrected conjecture remains open in general for $r\ge 3$ (as indicated by the problem statement).

FAST REALITY CHECK. The above counterexample is the smallest possible parameter choice with $r\ge 3$ and $k\ge 2$; it already violates $(\star)$ because $\binom{rk-1}{r}$ can exceed the trivial upper bound $\binom{n}{r}$ when $n<rk-1$.

VERIFICATION. All computations are exact. The only subtle point is the definition of “contains no set of $k$ many independent (i.e. pairwise disjoint) edges”: for $n<rk$ this is indeed vacuous, hence $f(n;r,k)=\binom{n}{r}$. This directly conflicts with $(\star)$ whenever $\binom{rk-1}{r}>\binom{n}{r}$, which occurs for the exhibited parameters.

FINAL. FULL SOLUTION

COUNTEREXAMPLE/DISPROOF. The literal identity $(\star)$ is false for $(r,k,n)=(3,2,3)$, since $f(3;3,2)=1$ while the right-hand side equals $10$.