we-solve (beta)

Math-887-A2 · revision r1 · on Math-887

gpt pro 5.2 attempt on Math-887

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 644 (transversals from local 2-piercing)
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK (browsing)
  4. ATTACK PLAN
  5. WORK
  6. Step 1: Hypergraph translation
  7. Step 2: Immediate consequence: bounded matching number
  8. Step 3: A simple universal upper bound via maximal matchings
  9. Step 4: Attempt to exploit the stronger local condition (incomplete)
  10. VERIFICATION
  11. FINAL
  12. COMPLETION ESTIMATE

Problem 644 (transversals from local 2-piercing)

FORMAL RESTATEMENT

Fix integers $k\ge 1$ and $r\ge 3$. Let $\mathcal A=\{A_1,\dots,A_m\}$ be a family of $k$-element subsets of some ground set $X$.

Assume the $(k,r)$-property with 2-piercing: for every choice of indices $i_1,\dots,i_r$, there exist elements $x,y\in X$ (depending on the $r$-tuple) such that \[ \{x,y\}\cap A_{i_j}\neq\varnothing\qquad\text{for all } j=1,\dots,r. \]

Let $f(k,r)$ be the least integer such that any such family $\mathcal A$ has a transversal (hitting set) $T\subseteq X$ with \[|T|\le f(k,r)\qquad\text{and}\qquad T\cap A_i\neq\varnothing\ \ \forall i. \]

The prompt records exact values for $r\in\{3,4,5,6\}$ and asks in particular:

  • determine/estimate $f(k,7)$ (conjectured $\sim \tfrac34 k$);
  • more generally, whether for each fixed $r$ there is a constant $c_r$ with $f(k,r)=(1+o(1))c_r k$ as $k\to\infty$.

QUICK LITERATURE/CONTEXT CHECK (browsing)

The prompt cites Erdős--Fűredi--Kostochka--Tuza $1992$ for the exact values \[f(k,3)=2k,\quad f(k,4)=\lfloor 3k/2\rfloor,\quad f(k,5)=\lfloor 5k/4\rfloor,\quad f(k,6)=k. \] A quick web check also turns up follow-up work on property $(p,2)$ transversals (e.g. papers by Fon-Der-Flaass and by Kostochka on general $(p,2)$ settings), but I did not locate a definitive resolution of the asymptotic for $r=7$ in freely accessible sources.

ATTACK PLAN

Translate to $k$-uniform hypergraphs and try to control the transversal number.
  1. (Definitions) View $\mathcal A$ as the edge set of a $k$-uniform hypergraph $H$.
  2. (Reduction) Note that the $(k,r)$-property implies $H$ has no matching of size $r$ (since $r$ disjoint edges cannot be hit by 2 vertices).
  3. (Known general inequality attempt) Relate transversal number $\tau(H)$ to matching number $\nu(H)$.
  4. (Try to use extra structure) The local "2-piercing" property is stronger than $\nu(H)\le r-1$; attempt to exploit it for $r=7$ (unsuccessful below).
  5. (Constructions) Consider families that make $\tau(H)$ large while keeping every $r$-edge subfamily 2-pierceable.

WORK

Step 1: Hypergraph translation

Let $H$ be the $k$-uniform hypergraph on vertex set $X$ with edge set $E(H)=\mathcal A$. Let $\tau(H)$ be its transversal (vertex cover) number and $\nu(H)$ its matching number. The definition of $f(k,r)$ is \[ f(k,r)= \max\{\tau(H):\ H\text{ is $k$-uniform and every $r$ edges are 2-pierceable}\}. \]

Step 2: Immediate consequence: bounded matching number

Lemma (No large matchings): If every $r$ edges of $H$ are hit by some 2-set, then $\nu(H)\le r-1$.
Proof: If $H$ had a matching of size $r$, i.e. $r$ pairwise disjoint edges $e_1,\dots,e_r$, then any hitting set for $\{e_1,\dots,e_r\}$ must contain at least one vertex from each $e_i$, hence has size at least $r>2$. This contradicts the assumed 2-piercing property for every $r$ edges. ∎

Step 3: A simple universal upper bound via maximal matchings

Lemma (Union of a maximal matching is a transversal): Let $M$ be a maximal matching in a hypergraph $H$. Then $U:=\bigcup_{e\in M} e$ is a transversal of $H$.
Proof: If some edge $f\in E(H)$ were disjoint from $U$, then $f$ is disjoint from every edge of $M$, so $M\cup\{f\}$ would be a larger matching. This contradicts maximality. ∎
Corollary (Linear bound): For any $k$ and $r$, \[ f(k,r) \le k(r-1). \]
Proof: Let $H$ satisfy the hypothesis. By the previous lemma, $\nu(H)\le r-1$. Take a maximal matching $M$; then $|M|\le r-1$ and the union $U$ is a transversal of size $|U|\le k|M|\le k(r-1)$. Hence $\tau(H)\le k(r-1)$, and taking the maximum over all such $H$ gives the claim. ∎

This bound is very weak compared to the exact values for $r\le 6$ (e.g. it gives $f(k,6)\le 5k$ whereas the true value is $k$).

Step 4: Attempt to exploit the stronger local condition (incomplete)

The obstacle is that $\nu(H)\le r-1$ only uses the fact that $r$ disjoint edges are forbidden, but does not capture the stronger condition "every $r$ edges have a 2-vertex cover". For $r=7$, one would like to show $\tau(H)\le (3/4+o(1))k$.

I attempted (unsuccessfully) to derive a structural lemma of the following flavour:

if $\tau(H)$ is large (linear with constant $>3/4$), then one can find $7$ edges whose minimum vertex cover is $\ge 3$.
The natural place to apply such a lemma is to a minimal transversal $T$ and the associated family of edges witnessing minimality, but I did not close the argument.

VERIFICATION

The proven inequalities are checked directly:
  • If there is a matching of size $r$, no 2-set can hit all $r$ disjoint edges.
  • The union of a maximal matching must hit every edge.

FINAL

UNRESOLVED.

Strongest fully proved partial result in this write-up:

For all $k\ge 1$ and $r\ge 3$, one always has the universal linear bound \[ f(k,r)\le k(r-1). \]
This shows at least that $f(k,r)=O_r(k)$ for fixed $r$, though it does not address the conjectured constants $c_r$ (e.g. $c_7=3/4$).

COMPLETION ESTIMATE

$0.25$.