# A problem with an edge labeling on the boolean lattices

Let $B_n$ be the boolean lattice of rank $n$. Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum, respectively.
We identify the notion of edge with the notion of interval $[a,b]$ of cardinal $2$.
We propose to label every edge with the symbols $\alpha$ or $\beta$, such that:

1. For every maximal chain, exactly one edge is labeled by $\alpha$.
2. For every element $a \in B_n$, $a \neq \hat{1}$, then at most one edge $[a,x]$ is labeled by $\alpha$.
(note that $x$ is an atom of the interval $[a, \hat{1}]$)

Question: Is there a coatom $y$ of $B_n$ such that the edge $[y,\hat{1}]$ is labeled by $\alpha$?

• It seems true by induction. Do cases of n=1 and 2 by hand if necessary. For n+1, there is at most one atom a above 0 with an alpha below it. The rest don't, so the maximal chain through another atom b must have an alpha in a maximal chain in the interval from b to 1. The hypothesis now gives an alpha above a coatom. Gerhard "Chains Of Edges And Deductions" Paseman, 2016.09.09. – Gerhard Paseman Sep 10 '16 at 4:41

Yes. For $n=1$, the result is clear as we must choose $\alpha$ for the one and only edge. For $n>1$, by the second condition there must be an atom $a \in B_n$ such that $[\hat 0, a]$ is not labeled with $\alpha$. Now for the first condition to hold every maximal chain in $[a, \hat 1] \cong B_{n-1}$ must have exactly one edge labeled with $\alpha$. Thus both conditions must hold for $[a, \hat 1] \cong B_{n-1}$. By induction a edge from a coatom of $[a, \hat 1]$ must be labeled with $\alpha$, the result follows since coatoms of $[a, \hat 1]$ are coatoms of $B_n$.

• I'm glad we agree. I suspect that one can prove by induction that the only such maps are "stilt" maps: Put one copy of Bn above another, connect with stilts, and label only the stilts with alphas. Gerhard "Striving For Ever Broader Perspectives" Paseman, 2016.09.09. – Gerhard Paseman Sep 10 '16 at 4:56
• @GerhardPaseman yes I now see your comment which must have been as I was answering. Perhaps something can be said about characterizing the labelings. After all into unique for n=1, and we have an induction. – John Machacek Sep 10 '16 at 5:17
• Unfortunately, the stilt maps are unique only if we insist that no member is above two edges labeled alpha. Other maps exist, including the map where alphas exist only above coatoms. Gerhard " Stops Walking On His Hands" Paseman, 2016.09.09. – Gerhard Paseman Sep 10 '16 at 5:23
• @GerhardPaseman: the answer I post, seems correspond with your comment. – Sebastien Palcoux Sep 10 '16 at 6:38

John Machacek's elegant answer solves the question, but we can also answer the question by characterizing all the labelings. For each labeling $\lambda$, consider a labeling $\pi$ of elements in $B_n$ such that $\pi(a)$ is the number of edges with label $\alpha$ on each chain from $\hat 0$ to $a$, for every $a\in B_n$. $\pi$ is well-defined as each chain from $\hat 0$ to $a$ must have the same number of edges with label $\alpha$. And the domain of $\pi$ is $\{0,1\}$ and $\pi$ is monotone, that for every $a,b\in B_n$, $a\geq b$ implies $\pi(a)\geq \pi(b)$. Let $S\subset B_n$ be the set of elements that $\pi(a)=1$. By monotony, $a\geq b$ and $b\in S$ implies $a\in S$. If $a$ and $b$ has the same cardinal and differ by exactly one element, in other words, there is element $c$ and distinct atoms $x$ and $y$ that $a=c\cup\{x\}$ and $b=c\cup\{x\}$, then $a\in S$ and $b\in S$ implies $c\in S$ by the second assumption in the problem. So by induction, $a\in S$ and $b\in S$ implies $(a\cap b)\in S$. So $S$ must be an interval $[c, \hat 1]$ for some $c\in B_n$. And evidently $[\hat 0, \hat1]$ does not correspond to any labeling $\lambda$ while any other $S=[c, \hat 1]$ corresponds to a valid labeling $\lambda$. So we can find an atom $x\not \in c$, and then the edge $[x^c, \hat 1]$ is labeled with $\alpha$.

• Your answer gives a nice understanding of what happens. – Sebastien Palcoux Sep 13 '16 at 9:52

If we add the following third condition:

1. For every element $b \in B_n$, $b \neq \hat{0}$, then at most one edge $[x,b]$ is labeled by $\alpha$.

Then we can prove:

Proposition: There exists an atom $a$ such that an edge $[x,y]$ is labeled by $\alpha$ iff $y=x \vee a$.

Proof: Let $\lambda$ be the labeling map. We start with an induction as for John's answer. If $n=1$ it is ok. We assume that it is true at rank $<n$ and we will prove for rank $n>1$. There exists an atom $s$ such that $\lambda([\hat{0},s]) = \beta$, then we can apply the induction on $[s,\hat{1}]$, and it follows the existence of an atom $a$ of $[\hat{0}, s^c]$ such that an edge $[x,y]$ of $[s,\hat{1}]$ is labeled by $\alpha$ iff $y=x \vee a$. So $\lambda([a^c,\hat{1}]) = \alpha$, then $\lambda([s^c,\hat{1}])=\beta$. We apply the induction again on $[\hat{0},s^c]$, it follows the existence of an atom $a'$ of $[\hat{0}, s^c]$ such that an edge $[x,y]$ of $[\hat{0}, s^c]$ is labeled by $\alpha$ iff $y=x \vee a'$. We just need to prove that $a'=a$. If $a \neq a'$ then there is a maximal chain starting by $[\hat{0},a']$ and finishing by $[a^c,\hat{1}]$, but both are labeled by $\alpha$, contradiction. $\square$