Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Unsigned-support matching fails for every maximum subset
This is a proved obstruction to an auxiliary approach, not a counterexample to the logarithmic lower bound.
Let
Every five-subset is dissociated. Indeed, a nonzero ternary relation involving at most five positive odd numbers must have support two or four. Support two is impossible. Support four would give equal sums of two distinct pairs, or an element equal to a sum of three others. The 21 pair sums are the distinct numbers
The only triple sums at most 55 are 49, 51, and 53, none in .
Every six-subset is dependent, as the following table certifies.
| Omitted element | Relation |
|---|---|
| 3 | |
| 15 | |
| 31 | |
| 33 | |
| 35 | |
| 41 | |
| 55 |
Consequently , and every five-subset is maximum. For a maximum and , let its unsigned-support neighborhood consist of the supports of all ternary representations . Maximality supplies at least one representation. Every representation uses all five coordinates: otherwise it would give a relation on at most five elements of . Both omitted elements therefore have neighborhood , violating Hall's condition for every maximum .
Thus optimizing the choice of maximum dissociated subset cannot repair unsigned-support matching. This does not refute the distinct complement-orbit matching assertion in the proof sketch: different full-support sign patterns correspond to different complement orbits there.
A valid single-exchange criterion
If is dissociated and , then
Indeed, a dependence on the replacement set must use , since is dissociated, and rearranges to a representation omitting . Conversely, such a representation gives a dependence. This permits every single exchange for an element with only full-support representations, but does not justify simultaneous exchanges.