3
$\begingroup$

Let $G(\mathcal{P}(n),E)$ be the undirected graph for the power set of $[n]$ elements under the inclusion relation (i.e. a poset). The width of this poset - which is defined as the size of the maximum antichain- is $k_1=\binom{n}{n/2}$( per Sperner's theorem when $n$ is even).

Let $H(\mathcal{P}(n),\hat{E})$ be a bipolar orientation of $G$. $H$ defines a poset with width $k_2$. Is it always the case that $k_1\geq k_2$? Because from trail and error and experimenting on $[3]$ it seems that's the case. Any hints would be appreciated.

$\endgroup$
  • $\begingroup$ I could be misunderstanding something, but doesn't Sperner's theorem mean that the $k_1$ is the size of the largest independent set in $G$? Wouldn't that then imply your result? $\endgroup$ – Tyler Seacrest Oct 9 '14 at 14:41
  • $\begingroup$ @TylerSeacrest Yes. but since I'm not mathematician I thought maybe there is a known result/reference for this. My proof is simple: assume $k_2=k_1+1$ then there is a vertex $v_0$ whose not in the layer (i.e. the largest independent set $\theta$) since its bipolar there must be a path from $v_0$ to the sink or source traversing over one element in $\theta$ therefore $k_2$ cannot be larger than $k_1$. $\endgroup$ – seteropere Oct 9 '14 at 19:03
  • $\begingroup$ Personally, I'm not really an expert on posets, so I don't have great reference for you. I will say for me translating this problem into graph theoretic terms (i.e. anti-chains are independent sets, H is the same as G except oriented and with added edges) makes the problem a lot clearer to me, since it then follows from the fact you can't increase the size of an independent set by adding edges. If you're curious, you can research comparability graphs. $\endgroup$ – Tyler Seacrest Oct 10 '14 at 14:47

Your Answer

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

Browse other questions tagged or ask your own question.