4
$\begingroup$

Let $L$ be a finite distributive lattice with minimum $0$ and Maximum $1$ and join-irreducible elements $j_1,...,j_l$ and meet irreducible elements $m_1,...,m_l$. Let $J_L:= \sum\limits_{i=1}^{l}{| [j_i,1]|}$ and $M_L:= \sum\limits_{i=1}^{l}{| [0,m_i]|}$. Set $X_L$:= $l-|J_L-M_L|$.

Question 1: Is there an easy proof that $X_L >0 $ ? This would prove Frankl's conjecture for distributive lattices (which is already known).

Question 2: What are the distributive lattices with $X_L=l$? Their number starts for $n \geq 3$ with 1,2,1,3,2,7,4. Examples are Boolean lattices.

Question 3: Let $U_n:= \sum\limits_{L \in \mathcal{L}_n}^{}{|J_L-M_L|}$, where $\mathcal{L}_n$ is the set of all distributive lattices on $n$ elements. $U_n/2$ starts for $n \geq 3$ with 0,0,1,2,6,12,34 (could it be https://oeis.org/A088808 ?). What is $U_n$?

$\endgroup$
  • $\begingroup$ It seems to me that there can't be any good description of lattices with $X_L = \ell$. We have $X_L = \ell$ whenever $L$ is isomorphic to its opposite lattice. If $P$ is any finite poset isomorphic to its opposite poset, then the lattice of lower ideal of $P$ is a lattice isomorphic to its opposite lattice. And there are tons of posets isomorphic to their opposites. $\endgroup$ – David E Speyer Jan 15 at 14:20
  • $\begingroup$ I'm also skeptical of a good answer to Q3, because the cardinality of $\mathcal{L}_n$ is intractable and therefore I would guess that summing more complicated quantities over it is as well. I realize this isn't a strong argument. $\endgroup$ – David E Speyer Jan 15 at 14:22
2
$\begingroup$

The proposed inequality $X_L>0$ is false. Using Birkhoff's representation theorem, identify $L$ with the lattice of lower ideals in a poset $P$. Then $|P| = \ell$.

The join irreducible elements are the principal lower ideals $(p)$ for $p \in P$. Given a join irreducible element $j=(p)$, the interval $[j,1]$ is the set of ideals $I$ containing $p$. Thus, $$J_L = \sum_{p \in P} \#\{ I : I \ni p \} = \sum_{I \in L} \#(I).$$ Similarly, $$M_L = \sum_{I \in L} (\ell - \#(I)).$$ So the proposed inequality is $$\left| \ell \#(L) - 2 \sum_{I \in L} \#(I) \right| < \ell.$$

Let the poset $P$ have $a+b$ elements $x_1$, $x_2$, ..., $x_a$, $y_1$, $y_2$, ..., $y_b$ and the relations that the $x$'s are incomparable, the $y$'s form a chain $y_1 < y_2 < \cdots < y_b$ and $x_i < y_j$ for all $i$, $j$. So the lower ideals are of two types:

(1) Any subset of the $x$'s.

(2) $\{x_1, x_2, \ldots, x_a, y_1, y_2, \ldots, y_k \}$ for $1 \leq k \leq b$.

We have $\ell = a+b$, $|L| = 2^a + b$ and $\sum_{I \in L} \#(I) = (a/2) 2^a + b (a+b/2+1/2)$. So $$\ell \#(L) - \sum_{I \in L} \#(I) = (a+b)(2^a+b) - (a 2^a + b(2a+b+1))$$ $$=b 2^a - b(a+1).$$

If we choose $a$ and $b$ roughly the same size, then $|b 2^a - b(a+1)|$ will be much larger than $a+b$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.