[combinatorics] combinatorial existence theorem (three combinatorial existence theorems | finite poset decomposition theorem | Ramsey theorem | existence theorem of different representative systems |

One 、 Combinatorial existence theorem

---

Combinatorial existence theorem There are three main theorems , Decomposition theorem of finite poset , Ramsey Theorem , Existence theorem of different representative systems ;

1. Decomposition theorem of finite poset :

• Posets

  <

  A

  ,

  ≼

  >

  <A , \preccurlyeq>

  <A,≼> in , The maximum chain length is

  n

  n

  n , Then the poset can be decomposed into at least

  n

  n

  n Disjoint anti chain ;

• Posets

  <

  A

  ,

  ≼

  >

  <A , \preccurlyeq>

  <A,≼> in , The maximum anti chain length is

  n

  n

  n , Then the poset can be decomposed into at least

  n

  n

  n A disjoint chain ;

A chain is a subset of a set , The elements of it Both are comparable , Anti chain is a subset of set , The elements of it Two cannot be compared ;

Reference resources : 【 Set theory 】 Order relations ( chain | Anti chain | Chain and anti chain examples | Chain and anti chain theorem | Chain and anti chain inference | Good order relationship ) Four 、 Chain and anti chain theorem ,

Posets

<

A

,

≼

>

<A , \preccurlyeq>

<A,≼> in , The maximum chain length is

n

n

n , Each time, the current maximal element is taken away and placed in a partition ,

n

n

n After that , Got it.

n

n

n Partition blocks , All elements have been allocated ;

2. Ramsey Theorem : The theorem is Extension of pigeon nest principle , In essence, the generalization is to determine the existence of a combination configuration ;

3. Existence theorem of different representative systems :Hall Theorem ;

Bipartite graph : The nodes of the graph are divided into

X

,

Y

X , Y

X,Y Two parts ,

X

X

X There are no edges inside the set ,

Y

Y

Y There are no edges inside the set , All sides are from

X

X

X The collection is connected to

Y

Y

Y aggregate ;

Perfect match : In a bipartite graph, there is a Complete matching , stay

X

X

X Each node in the collection can be found

Y

Y

Y Matching nodes in the collection ;

Conclusion :

X

X

X Subset of the corresponding

Y

Y

Y Number of nodes in the set , No better than this

X

X

X The number of subsets is small ;

Two 、Ramsey Summary of theorem content

---

Pigeon nest principle :

• Simple form
• General form

Based on the pigeon nest principle , obtain Ramsey Theorem ;

Ramsey Theorem :

• Simple form
• Small Ramsey Count
• General form
• Ramsay Number of known results