Cut family

In mathematics, an intersection family of a set describes a family of subsets of , in which two of its elements each have a non-empty intersection. ${\displaystyle N}$ ${\displaystyle N}$

definition

A set family is called a section family if the following property is met: ${\displaystyle F\subseteq {\mathcal {P}}(N)}$

For all true . ${\displaystyle A_{i},A_{j}\in F}$ ${\displaystyle A_{i}\cap A_{j}\neq \varnothing }$

Remarks

The maximum thickness of an intersecting family of a finite set of the thickness is . ${\displaystyle F}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle |F|\leq 2^{n-1}}$

Each filter is a cut family.

A pattern family describes a pattern family in which all elements have the thickness . Erdős-Ko-Rado's theorem makes a statement about the maximum thicknesses of such families . ${\displaystyle k}$ ${\displaystyle k}$

According to Kleitman's theorem , the union of intersecting families has at most subsets. ${\displaystyle m}$ ${\displaystyle {\bar {F}}=\bigcup _{i=1}^{m}F_{i}}$ ${\displaystyle |{\bar {F}}|\leq 2^{n}-2^{n-m}}$

swell

• Martin Aigner , Günter M. Ziegler : The BOOK of evidence . Springer, Berlin 2002, ISBN 3-540-42535-7 (3rd edition: ISBN 978-3-642-02258-6 )
• Stasys Jukna : Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4 .

Individual evidence

1. ↑ Stasys Jukna : Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4 , p. 90.
2. ↑ Stasys Jukna : Extremal Combinatorics. Springer, Berlin 2001, ISBN 3-540-66313-4 , p. 91.