Here is the third research thread for the polynomial Hirsch conjecture. I hope that people will feel as comfortable as possible to offer ideas about the problem we discuss. Even more important, to think about the problem either in the directions suggested by others or on their own. Participants who follow the project and think about the issues without adding remarks are valuable.
The combinatorial problem is simple to state and also everything that we know about it is rather simple. At this stage joining the project should be easy.
Let me try to describe (without attemting to be complete) one main direction that we discuss. This direction started with the very first comment we had by Nicolai.
Please do not hesitate to repeat an idea raised by yourself or by other if you think it can be useful.
Thinking about multisets (monomials).
Let be the largest number of disjoint families of degree d monomials in the variables such that
(*) for i < j < k, whenever and , then there exists a monomial such that .
The example that supports this conjecture consists of families with a single monomial in every family.
The monomials are
There are other examples that achieve the same bound. The bound can be achieved by families whose union include all monomials, and for such families the conjecture is correct.
The case d=3.
An upper bound by EHRR (that can be extended to monomials) following works of Barnette and Larman on polytopes is . For degree 3 monomials we have a gap
It may be the case that understanding the situation for is the key for the whole problem.
There is another example achieving the lower bound that Terry found
More examples, please…
Various approaches to the conjecture
Several approaches to the cojecture were proposed. Using clever reccurence relations, finding useful ordering, applying the method of compression, and algebraic methods. In a series of remarks Tim is trying to prove Nicolai’s conjecture. An encouraging sign is that both examples of Nicolai, Klas, and Terry come up naturally. One way to help the project at this stage would be to try to enter Tim’s mind and find ways to help him “push the car”. In any case, if Nicolai’s conjecture is correct I see no reason why it shouldn’t have a simple proof (of course we will be happy with long proofs as well).
Something that is also on the back of our minds is the idea to find examples that are inspired from the upper bound proofs. We do not know yet what direction is going to prevail so it is useful to remember that every proof of a weaker result and every difficulty in attempts to proof the hoped-for result can give some ideas for disproving what we are trying to prove.
Some preliminary attempts were made to examine what are the properties of examples for d=3 which will come close to the 4n bound. It may also be the case that counterexamples to Nicolai’s conjecture can be found for rather small values of n and d.