Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Proof
Use the conventions of L187. Write , and . A selected set of clone points covers every expanded edge if and only if the original points whose classes contain at least selected clones form a transversal of . If these original points miss an edge, choose an -subset avoiding the selection in each of that edge's classes. Conversely, an edge meeting one of the specified classes cannot avoid the selection. Therefore
A repeated-edge obstruction for each individual seed
Consider the complete clone-class operation defined on the claim card. If the seed is nonempty and has no empty edge, then
To prove this, index seven rows by the points of the Fano plane. The complements of its seven lines are four-point caps. Each row index belongs to four caps, and two caps never cover all seven row indices, since two lines intersect. Put . In each clone class, take copies of each cap as the incidence spectra of clone points; any remaining clone points have empty spectrum. Every row initially has points in the class. Delete memberships until each row has exactly points. Every surviving spectrum is a subset of a cap, so no two spectra cover all seven rows, even when the points come from different classes.
Fix one nonempty seed edge and make these same choices in every class indexed by . The resulting seven rows are edges of the expanded family. No two clone points meet them all. If some rows coincide, delete duplicates; covering the distinct rows is equivalent to covering the original list. Thus a subfamily of at most seven distinct edges has no two-point transversal, proving (). Under an exactly-seven convention, this also witnesses failure whenever the expanded family has at least seven edges, by extending that subfamily. In () it does have at least seven: already the choices in one nonempty class give .
Consequently a expansion must have . Combining this with the exact transversal formula above gives the necessary bound
Here are integers, so , and . Unlike the universal preservation criterion, (*) applies to each fixed seed individually.
For the parity family on the claim card, and : is a transversal, since every edge meets oddly and has even size . Thus for . Already (**), for every complete clone-class expansion with , gives
There is a stronger parity-specific obstruction covering the small clone sizes too:
Construct seven seed edges indexed by . Start with vertices of each of seven types , whose incidence spectra are modulo seven, and one extra vertex. Every row initially has vertices. Choose a set of of the typed vertices as follows: choose one vertex each of types and , and an even number of vertices of each other type. This is possible because the remaining is even and for ; each of the five even counts can range from zero to .
Before further modification, row zero has even intersection with , and the other six rows have odd intersection: modulo two the selected spectra are and , whose symmetric difference consists of those six rows. Remove row zero from the spectrum of the chosen type-zero vertex, and give the extra vertex spectrum . Row sizes remain , and now every row meets oddly. These are seven distinct edges of the parity family on vertices. Every vertex occurs in at most four of them. The chosen has the prescribed size, so relabeling realizes the same tuple for any specified set of that size.
If , four -subsets of an -point class can have empty intersection: their four complements have size and can cover the class because . To construct them, partition the class into four parts of size at most , and enlarge each part to that size. At every vertex appearing in four of the seed rows, use these four -subsets for the four corresponding expanded rows. At the other vertices use arbitrary -subsets. Every clone point then occurs in at most three of the seven expanded rows. Two points cover at most six rows. This proves (***), and the seven rows remain distinct because their projections are the seven distinct seed edges.
Thus any complete clone-class expansion of this parity seed must have , and its ratio obeys
For , , so this ratio is at most . For , the necessary condition forces , the unchanged seed. Hence no nontrivial complete clone-class substitution of a parity seed preserves both and its ratio above .