[combinatorics] Introduction to Combinatorics (combinatorial idea 3: upper and lower bound approximation | upper and lower bound approximation example Remsey number)

One 、 Combination thought 3 : The upper and lower bounds approach

---

The upper and lower bounds approach Thought , Usually used for Determine a value , or Determine the order of a function ( The magnitude of the function ) ;

The upper and lower bounds approach step :

( 1 ) Upper bound of proof value

( 2 ) Lower bound of proof value

( 3 ) If The upper and lower bounds are equal , be End of proof

( 4 ) If The upper and lower bounds are not equal , be Improve the upper bound or Lower bound , Make these two values gradually approximate ;

The value of many combinatorial numbers in combinatorics , Some upper and lower bounds are equal , The exact value is obtained , Some only get the upper and lower bounds of combinatorial numbers , also The upper and lower bounds are not equal , The specific value is unknown ;

Two 、 Examples of upper and lower bounds approximation ( Remsey Count )

---

Remsey ( Lemsy ) Count

K

n

K_n

Kn​ It's completely

n

n

n Order graph , The complete graph is There is an edge between each pair of different vertices , That is, each vertex has edges connected to all other vertices ;

Use red and blue , Yes

K

n

K_n

Kn​ Color the edges of , seek In coloring , appear A red triangle or A blue triangle Of

n

n

n The minimum value of ;

The result is

6

6

6 ;

This

6

6

6 It's the upper bound ;

Yes

K

6

K_6

K6​ Complete the painting , No matter how you paint , Will appear A red triangle or A blue triangle ;

K

6

K_6

K6​ Completely in the figure , According to the definition of complete graph , There is an edge between each pair of different vertices ,

Each vertex is associated with five edges , this

5

5

5 side , Two colors must be used for this

5

5

5 side Paint , Red or Blue , Edges of the same color have at least

3

3

3 strip ( perhaps

3

3

3 Red bar , perhaps

3

3

3 Bar blue ) ,

1. Suppose that the edge associated with the vertex has

3

3

3 The bar is red , The following figure shows a vertex leading out

3

3

3 A red edge , The three vertices at the other end of the three red edges , There are three sides , Next, we will discuss the situation of these three sides :

If all three sides are blue , Here's the picture , Then form a blue triangle ;

If there is a red edge on three sides , Here's the picture , Then form a red triangle ;

2. Suppose that the edge associated with the vertex has

3

3

3 The bar is blue , The following figure shows a vertex leading out

3

3

3 A blue edge , The three vertices at the other end of the three blue edges , There are three sides , Next, we will discuss the situation of these three sides :

If all three sides are red , Here's the picture , Then form a red triangle ;

Suppose there is a blue edge on three sides , Here's the picture , Then form a blue triangle ;

K

n

K_n

Kn​ Complete graph in general

n

=

6

n = 6

n=6 The value is the upper bound ,

n

=

7

n = 7

n=7 No problem ;

The upper bound problem is determined , Now let's discuss the lower bound ;

Discuss

n

=

5

n = 5

n=5 The situation of :

Give a counterexample , In the painting scheme in the figure below , There is no blue triangle , There is no red triangle , therefore

n

=

5

n=5

n=5 when , “ appear A red triangle or A blue triangle ” Don't set up ;

therefore

n

=

6

n=6

n=6 It's the lower boundary , There can be no comparison

6

6

6 Small value ;