1
$\begingroup$

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$?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 10, 2016 at 4:41

3 Answers 3

2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Sep 10, 2016 at 4:56
  • $\begingroup$ @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. $\endgroup$ Sep 10, 2016 at 5:17
  • $\begingroup$ 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. $\endgroup$ Sep 10, 2016 at 5:23
  • $\begingroup$ @GerhardPaseman: the answer I post, seems correspond with your comment. $\endgroup$ Sep 10, 2016 at 6:38
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Your answer gives a nice understanding of what happens. $\endgroup$ Sep 13, 2016 at 9:52
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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