Lagmental Vicfred

Hall's Condition Is a Set-System Inequality by Vicfred

tags: mathematics, posets, Mobius functions, extremal set theory

A family has distinct representatives exactly when every subfamily collectively contains enough possible representatives. A small computation will anchor the general statement before the abstraction takes over.

Definitions first

A finite poset \((P,\le)\) has intervals \([x,y]\) and an incidence algebra. Chains, antichains, and order ideals reveal different slices of its comparability structure.

$$ \mathcal A=(A_1,\ldots,A_n) $$

The first display fixes the mathematical data. I label it \(\mathsf{data}\) mentally, while the next is the \(\mathsf{claim}\); the bridge between them is the displayed \(\Longrightarrow\), not an automatic implication.

$$ \exists\,x_i\in A_i\ \text{all distinct}\Longleftrightarrow\left|\bigcup_{i\in I}A_i\right|\ge|I|\ \forall I\subseteq[n] $$

A small case in full

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ \begin{array}{c|ccc}i&1&2&3\\\hline A_i&\{a,b\}&\{b,c\}&\{a,c\}\end{array}\qquad(x_1,x_2,x_3)=(a,b,c) $$

The reusable statement

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad \mathcal A=(A_1,\ldots,A_n),\\[5pt] \mathsf{C}\;&:\quad \exists\,x_i\in A_i\ \text{all distinct}\Longleftrightarrow\left|\bigcup_{i\in I}A_i\right|\ge|I|\ \forall I\subseteq[n]. \end{aligned} $$

A nearby false statement

Width and height refer to antichains and chains in the poset, not to geometric dimensions of a drawing.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \exists\,x_i\in A_i\ \text{all distinct}\Longleftrightarrow\left|\bigcup_{i\in I}A_i\right|\ge|I|\ \forall I\subseteq[n] \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Tue 12 December 2017. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.