Wiki
Wiki

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

P={3,15,31,33,35,41,55}.P=\{3,15,31,33,35,41,55\}.

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

18,34,36,38,44,46,48,50,56,58,64,66,68,70,72,74,76,86,88,90,96.18,34,36,38,44,46,48,50,56,58,64,66,68,70,72,74,76,86,88,90,96.

The only triple sums at most 55 are 49, 51, and 53, none in PP.

Every six-subset is dependent, as the following table certifies.

Omitted elementRelation
315+35+55=31+33+4115+35+55=31+33+41
153+41+55=31+33+353+41+55=31+33+35
313+33+55=15+35+413+33+55=15+35+41
3335+55=3+15+31+4135+55=3+15+31+41
353+31+55=15+33+413+31+55=15+33+41
4131+55=3+15+33+3531+55=3+15+33+35
553+35+41=15+31+333+35+41=15+31+33

Consequently d(P)=5d(P)=5, and every five-subset is maximum. For a maximum D⊂PD\subset P and a∈P∖Da\in P\setminus D, let its unsigned-support neighborhood consist of the supports of all ternary representations a=∑d∈Dεdda=\sum_{d\in D}\varepsilon_d d. Maximality supplies at least one representation. Every representation uses all five coordinates: otherwise it would give a relation on at most five elements of PP. Both omitted elements therefore have neighborhood {D}\{D\}, violating Hall's condition for every maximum DD.

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 DD is dissociated and a∉Da\notin D, then

D∖{di}∪{a} is dissociated⟺every ternary representation of a on D uses di.D\setminus\{d_i\}\cup\{a\}\text{ is dissociated} \quad\Longleftrightarrow\quad \text{every ternary representation of }a\text{ on }D\text{ uses }d_i.

Indeed, a dependence on the replacement set must use aa, since D∖{di}D\setminus\{d_i\} is dissociated, and rearranges to a representation omitting did_i. 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.