The Sauer-Shelah-Perles inequality and relatively complemented lattices: the SSP=RC conjecture

Abstract

In this dissertation, we discuss a conjecture that a finite lattice satisfies the Sauer-Shelah-Perles inequality (SSP) if and only if it is relatively complemented (RC). It is straightforward to prove that SSP implies RC, and it is the other direction that is problematic. Our main advance in this direction is that a subset in an RC lattice, whose order-ideal of non-shattered elements has at most three minimal elements, satisfies the SSP inequality, that is, shatters at least as many elements as it has. Additionally, we show that our proof strategy does not work for five minimal elements and construct some tools that aim at disproving the conjecture