Ch. 11: Ramsey Numbers

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 11.1. The Ramsey Number of Graphs 11.2. Turán's Theorem 11.3. Exploration: Modified Ramsey Numbers 11.4. Excursion: Erdős Numbers

87 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

Putnam competition, 1953. Every edge of K6K_6K6 is colored red or blue. What can you always find?
3 vertices whose 3 joining edges all have the same color (a monochromatic triangle). This problem is the starting point of Ramsey numbers in graph theory.
Who was Frank Ramsey, and which of his papers led to the theory named after him?
An English mathematician (born 1903 in Cambridge, died 1930 aged 26); his paper “On a problem of formal logic”. His main interest was philosophy; he also worked on economics (probability, taxation, optimal saving).
Ramsey's Theorem (general form) For any k+1≥3k + 1 \ge 3k+1≥3 positive integers t,n1,…,nkt, n_1, \dots, n_kt,n1,…,nk there is a positive integer nnn such that if each ttt -element subset of {1,…,n}\{1, \dots, n\}{1,…,n} is colored with one of the kkk colors 1,…,k1, \dots, k1,…,k , then … ?
For some color iii there is a set S⊆{1,…,n}S \subseteq \{1, \dots, n\}S⊆{1,…,n} with nin_ini elements all of whose ttt -element subsets have color iii .
Ramsey's Theorem: for t,n1,…,nkt, n_1, \dots, n_kt,n1,…,nk there is an nnn such that whenever the ttt -element subsets of {1,…,n}\{1, \dots, n\}{1,…,n} get colors 1,…,k1, \dots, k1,…,k , some nin_ini -element set has all its ttt -element subsets colored iii .For t=1t = 1t=1 (coloring single elements, e.g. the vertices of KnK_nKn ), which nnn works, and why?
n=1+∑i=1k(ni−1)\boldsymbol{n = 1 + \sum_{i=1}^{k} (n_i - 1)}n=1+∑i=1k(ni−1) , by the Pigeonhole Principle. If every color iii had at most ni−1n_i - 1ni−1 elements, there would be at most ∑(ni−1)<n\sum (n_i - 1) < n∑(ni−1)<n elements.
Ramsey's Theorem for edges (Theorem 11.2) For any k≥2k \ge 2k≥2 positive integers n1,…,nkn_1, \dots, n_kn1,…,nk there is a positive integer nnn such that if each edge of KnK_nKn is colored with one of the colors 1,…,k1, \dots, k1,…,k , then … ?
For some iii there is a complete subgraph KniK_{n_i}Kni all of whose edges have color iii . This is the general form with t=2t = 2t=2 : the 2-element subsets of {1,…,n}\{1, \dots, n\}{1,…,n} are the edges of KnK_nKn .
What does Ramsey's Theorem say, in nontechnical words?
Every sufficiently large structure, however disorderly, contains an orderly substructure of any prescribed size.
What is a red-blue coloring of a graph GGG , and what is a red FFF in it?
Each edge of GGG gets red or blue. A red FFF is a subgraph isomorphic to FFF whose edges are all red. A blue FFF likewise. A coloring can contain a red F1F_1F1 , a blue F2F_2F2 , both or neither.
For nonempty graphs F1F_1F1 , F2F_2F2 (each with at least one edge), what is the Ramsey number r(F1,F2)r(F_1, F_2)r(F1,F2) ?
The smallest nnn such that every red-blue coloring of KnK_nKn contains a red F1F_1F1 or a blue F2F_2F2 .
Why does the Ramsey number r(F1,F2)r(F_1, F_2)r(F1,F2) (smallest nnn with a red F1F_1F1 or a blue F2F_2F2 in every red-blue KnK_nKn ) exist for all nonempty graphs F1,F2F_1, F_2F1,F2 ?
By Ramsey's Theorem, a large enough red-blue KnK_nKn has a red KsK_sKs or a blue KtK_tKt , where sss and ttt are the orders of F1F_1F1 and F2F_2F2 . A red KsK_sKs contains a red F1F_1F1 , a blue KtK_tKt a blue F2F_2F2 .
To prove that the Ramsey number r(F1,F2)=nr(F_1, F_2) = nr(F1,F2)=n , which two statements must you verify?
(1) Every red-blue coloring of KnK_nKn has a red F1F_1F1 or a blue F2F_2F2 ; (2) some red-blue coloring of Kn−1K_{n-1}Kn−1 has neither. (1) shows r(F1,F2)≤nr(F_1, F_2) \le nr(F1,F2)≤n , (2) shows r(F1,F2)≥nr(F_1, F_2) \ge nr(F1,F2)≥n .
r(K3,K3)= ?r(K_3, K_3) = \; ?r(K3,K3)=?
6\boldsymbol{6}6 Party version: 6 people guarantee 3 mutual acquaintances or 3 mutual strangers (vertices = people, red edge = acquainted, blue edge = strangers).
Why does every red-blue coloring of K6K_6K6 contain a red K3K_3K3 or a blue K3K_3K3 ?
Pigeonhole at one vertex v1v_1v1 : 3 of its 5 edges have the same color, say red v1v2,v1v3,v1v4v_1v_2, v_1v_3, v_1v_4v1v2,v1v3,v1v4 . A red edge among v2,v3,v4v_2, v_3, v_4v2,v3,v4 gives a red K3K_3K3 ; otherwise v2,v3,v4v_2, v_3, v_4v2,v3,v4 form a blue K3K_3K3 .
Which red-blue coloring of K5K_5K5 shows that r(K3,K3)≥6r(K_3, K_3) \ge 6r(K3,K3)≥6 ?
A red 5-cycle (v1,v2,…,v5,v1)(v_1, v_2, \dots, v_5, v_1)(v1,v2,…,v5,v1) , all other edges blue. The blue edges form another 5-cycle; neither 5-cycle contains a triangle. Bold edges are red.
F1F_1F1 and F2F_2F2 are nonempty graphs of orders n1n_1n1 and n2n_2n2 . What lower bound holds for the Ramsey number r(F1,F2)r(F_1, F_2)r(F1,F2) , and why?
r(F1,F2)≥max⁡{n1,n2}\boldsymbol{r(F_1, F_2) \ge \max\{n_1, n_2\}}r(F1,F2)≥max{n1,n2} Say n1≥n2n_1 \ge n_2n1≥n2 . Color all of Kn1−1K_{n_1 - 1}Kn1−1 red: it has too few vertices for a red F1F_1F1 , and no blue edge at all.
For t≥2t \ge 2t≥2 , r(K2,Kt)= ?r(K_2, K_t) = \; ?r(K2,Kt)=?
t\boldsymbol{t}t ≥t\ge t≥t since ttt is the larger order. ≤t\le t≤t : in a red-blue KtK_tKt , any red edge is a red K2K_2K2 ; otherwise the whole KtK_tKt is blue.
Why is r(F1,F2)=r(F2,F1)r(F_1, F_2) = r(F_2, F_1)r(F1,F2)=r(F2,F1) for Ramsey numbers?
The colors are irrelevant: swapping red and blue turns “red F1F_1F1 or blue F2F_2F2 ” into “red F2F_2F2 or blue F1F_1F1 ”. So, e.g., r(Kt,K2)=r(K2,Kt)=tr(K_t, K_2) = r(K_2, K_t) = tr(Kt,K2)=r(K2,Kt)=t .
How many people must be at a party to guarantee three mutual acquaintances or four mutual strangers?
9=r(K3,K4)\boldsymbol{9 = r(K_3, K_4)}9=r(K3,K4) People are the vertices of KnK_nKn ; red edge = acquainted, blue edge = strangers.
Why does every red-blue coloring of K9K_9K9 have a vertex with at least 4 red edges or at least 6 blue edges?
Not every vertex can have exactly 3 red edges: the red subgraph would be a 3-regular graph of order 9, which doesn't exist (it would have 9 odd vertices). So some vertex has ≥4\ge 4≥4 red edges, or ≤2\le 2≤2 red and hence ≥6\ge 6≥6 blue of its 8 edges.
In every red-blue coloring of K9K_9K9 some vertex v1v_1v1 has 4 red edges or 6 blue edges. Also r(K3,K3)=6r(K_3, K_3) = 6r(K3,K3)=6 .How does each case give a red K3K_3K3 or a blue K4K_4K4 ?
4 red neighbors: any red edge among them gives a red K3K_3K3 , else they form a blue K4K_4K4 . 6 blue neighbors: they span a K6K_6K6 with a red K3K_3K3 or a blue K3K_3K3 , and v1v_1v1 extends a blue K3K_3K3 to a blue K4K_4K4 . This shows r(K3,K4)≤9r(K_3, K_4) \le 9r(K3,K4)≤9 .
Which red-blue coloring of K8K_8K8 shows that r(K3,K4)≥9r(K_3, K_4) \ge 9r(K3,K4)≥9 ?
Blue subgraph C82C_8^2C82 (each vertex of an 8-cycle joined to the 2 nearest vertices on each side), red subgraph its complement. It has no red K3K_3K3 and no blue K4K_4K4 .
Restate the Ramsey number r(F1,F2)r(F_1, F_2)r(F1,F2) without colors, using a graph GGG and its complement G‾\overline{G}G .
The smallest nnn such that for every graph GGG of order nnn , GGG contains F1F_1F1 or G‾\overline{G}G contains F2F_2F2 . Red edges form GGG , blue edges form G‾\overline{G}G .
The Ramsey numbers r(Ks,Kt)r(K_s, K_t)r(Ks,Kt) , written r(s,t)r(s, t)r(s,t) , are called the classical Ramsey numbers.
They were the first Ramsey numbers to be studied extensively.
Express the classical Ramsey number r(s,t)=r(Ks,Kt)r(s, t) = r(K_s, K_t)r(s,t)=r(Ks,Kt) using complete subgraphs and independent sets.
The smallest nnn such that every graph of order nnn contains KsK_sKs or an independent set of ttt vertices. A set SSS with G[S]=KtG[S] = K_tG[S]=Kt in G‾\overline{G}G is an independent set of GGG .
r(K3,K4)=9r(K_3, K_4) = 9r(K3,K4)=9 .A graph GGG of order 9 contains no K4K_4K4 . What must GGG contain?
An independent set of 3 vertices. r(K4,K3)=r(K3,K4)=9r(K_4, K_3) = r(K_3, K_4) = 9r(K4,K3)=r(K3,K4)=9 : every graph of order 9 contains K4K_4K4 or 3 mutually nonadjacent vertices.
Which classical Ramsey numbers r(s,t)r(s, t)r(s,t) with 3≤s≤t3 \le s \le t3≤s≤t are known (as of the book)?
r(3,t)r(3, t)r(3,t) for t=3,…,9t = 3, \dots, 9t=3,…,9 : 6, 9, 14, 18, 23, 28, 36; and r(4,4)=18r(4, 4) = 18r(4,4)=18 , r(4,5)=25r(4, 5) = 25r(4,5)=25 . Only these nine.
Is the classical Ramsey number r(5,5)=r(K5,K5)r(5, 5) = r(K_5, K_5)r(5,5)=r(K5,K5) known?
No: only 43≤r(5,5)≤4943 \le r(5, 5) \le 4943≤r(5,5)≤49 . Known bounds are often far apart: 798≤r(10,10)≤12 677798 \le r(10, 10) \le 12\,677798≤r(10,10)≤12677 .
r(P3,K3)= ?r(P_3, K_3) = \; ?r(P3,K3)=? , and which red-blue coloring of K4K_4K4 shows the lower bound?
5\boldsymbol{5}5 ; red perfect matching, blue 4-cycle. Red (bold) v1v4v_1v_4v1v4 , v2v3v_2v_3v2v3 : no red P3P_3P3 . The blue C4C_4C4 has no triangle.
Why does every red-blue coloring of K5K_5K5 contain a red P3P_3P3 or a blue K3K_3K3 ?
A vertex v1v_1v1 with 2 red edges gives a red P3P_3P3 ; otherwise v1v_1v1 has 3 blue edges, to v2,v3,v4v_2, v_3, v_4v2,v3,v4 say. A blue edge among v2,v3,v4v_2, v_3, v_4v2,v3,v4 gives a blue K3K_3K3 ; otherwise v2v3v_2v_3v2v3 , v3v4v_3v_4v3v4 form a red P3P_3P3 .
r(K1,3,K3)= ?r(K_{1,3}, K_3) = \; ?r(K1,3,K3)=? , and which red-blue coloring of K6K_6K6 shows the lower bound?
7\boldsymbol{7}7 ; red subgraph 2K32K_32K3 , blue subgraph K3,3K_{3,3}K3,3 . Each vertex has only 2 red edges (no red K1,3K_{1,3}K1,3 ), and the bipartite K3,3K_{3,3}K3,3 has no triangle.
Why does every red-blue coloring of K7K_7K7 contain a red K1,3K_{1,3}K1,3 or a blue K3K_3K3 ?
Without a red K1,3K_{1,3}K1,3 , a vertex v1v_1v1 has at most 2 red edges, so at least 4 blue ones, to v2,…,v5v_2, \dots, v_5v2,…,v5 say. A blue edge among v2,…,v5v_2, \dots, v_5v2,…,v5 gives a blue K3K_3K3 ; if all are red, then v2v3,v2v4,v2v5v_2v_3, v_2v_4, v_2v_5v2v3,v2v4,v2v5 form a red K1,3K_{1,3}K1,3 .
Theorem 11.8 (Chvátal, 1977) For every tree TmT_mTm of order m≥2m \ge 2m≥2 and every integer n≥2n \ge 2n≥2 , r(Tm,Kn)= ?r(T_m, K_n) = \; ?r(Tm,Kn)=?
(m−1)(n−1)+1\boldsymbol{(m - 1)(n - 1) + 1}(m−1)(n−1)+1 Published in the very first issue of the Journal of Graph Theory. E.g. r(P3,K3)=5r(P_3, K_3) = 5r(P3,K3)=5 and r(K1,3,K3)=7r(K_{1,3}, K_3) = 7r(K1,3,K3)=7 .
r(Tm,Kn)=(m−1)(n−1)+1r(T_m, K_n) = (m-1)(n-1) + 1r(Tm,Kn)=(m−1)(n−1)+1 for every tree TmT_mTm of order m≥2m \ge 2m≥2 and every n≥2n \ge 2n≥2 .Which red-blue coloring of K(m−1)(n−1)K_{(m-1)(n-1)}K(m−1)(n−1) proves the lower bound?
Red subgraph: n−1n - 1n−1 disjoint copies of Km−1K_{m-1}Km−1 . Blue subgraph: the complete (n−1)(n-1)(n−1) -partite graph Km−1,…,m−1K_{m-1, \dots, m-1}Km−1,…,m−1 . Red components have only m−1m - 1m−1 vertices, so there is no red tree of order mmm . Any nnn vertices include two in the same partite set, so there is no blue KnK_nKn .
If δ(G)≥m−1\delta(G) \ge m - 1δ(G)≥m−1 (minimum degree), then GGG contains every tree of order mmm .Proving r(Tm,Kn)≤(m−1)(n−1)+1r(T_m, K_n) \le (m-1)(n-1) + 1r(Tm,Kn)≤(m−1)(n−1)+1 by induction on nnn : how does a red-blue K(m−1)k+1K_{(m-1)k+1}K(m−1)k+1 get a red TmT_mTm (tree of order mmm ) or a blue Kk+1K_{k+1}Kk+1 ?
Either some vertex v1v_1v1 has (m−1)(k−1)+1(m-1)(k-1) + 1(m−1)(k−1)+1 blue edges, or the red subgraph has minimum degree ≥m−1\ge m - 1≥m−1 . Case 1: the blue neighbors of v1v_1v1 span a K(m−1)(k−1)+1K_{(m-1)(k-1)+1}K(m−1)(k−1)+1 , which by induction has a red TmT_mTm or a blue KkK_kKk ; with v1v_1v1 a blue KkK_kKk becomes a blue Kk+1K_{k+1}Kk+1 .Case 2: each vertex has degree (m−1)k(m-1)k(m−1)k , at most (m−1)(k−1)(m-1)(k-1)(m−1)(k−1) of it blue, so at least m−1m - 1m−1 red edges; the r…
r(K1,s,Kt)= ?r(K_{1,s}, K_t) = \; ?r(K1,s,Kt)=? (for s≥1s \ge 1s≥1 , t≥2t \ge 2t≥2 )
s(t−1)+1\boldsymbol{s(t - 1) + 1}s(t−1)+1 The star K1,sK_{1,s}K1,s is a tree of order m=s+1m = s + 1m=s+1 , and r(Tm,Kt)=(m−1)(t−1)+1r(T_m, K_t) = (m-1)(t-1) + 1r(Tm,Kt)=(m−1)(t−1)+1 .
r(K1,3,C4)= ?r(K_{1,3}, C_4) = \; ?r(K1,3,C4)=? , and which red-blue coloring of K5K_5K5 shows the lower bound?
6\boldsymbol{6}6 ; a red 5-cycle, the other 5 edges (another 5-cycle) blue. Each vertex has 2 red edges (no red K1,3K_{1,3}K1,3 ), and C5C_5C5 contains no C4C_4C4 .
r(K3,K3)=6r(K_3, K_3) = 6r(K3,K3)=6 .Why does every red-blue coloring of K6K_6K6 contain a red K1,3K_{1,3}K1,3 or a blue C4C_4C4 ?
Start from a monochromatic triangle v1v2v3v_1v_2v_3v1v2v3 . Red triangle: a red edge from v1,v2v_1, v_2v1,v2 or v3v_3v3 to {v4,v5,v6}\{v_4, v_5, v_6\}{v4,v5,v6} would make a red K1,3K_{1,3}K1,3 , so all 9 such edges are blue, a blue K3,3⊇C4K_{3,3} \supseteq C_4K3,3⊇C4 .Blue triangle: each of v4,v5,v6v_4, v_5, v_6v4,v5,v6 has exactly 1 blue edge to it (2 give a blue C4C_4C4 , 0 a red K1,3K_{1,3}K1,3 ). Then a red edge among v4,v5,v6v_4, v_5, v_6v4,v5,v6 gives a red K1,3K_{1,3…
Which triangle-free graph of order 4 has the most edges, and how many edges force a triangle in order 4?
C4C_4C4 (size 4), the only triangle-free graph of order 4 and size 4. Size 5 forces a triangle. G1=K4−eG_1 = K_4 - eG1=K4−e is the only graph of order 4 and size 5. H=K2,3H = K_{2,3}H=K2,3 : order 5, size 6, no triangle.
Mantel's theorem (1907) If GGG is a graph of order n≥3n \ge 3n≥3 and size m> ?m > \; ?m>? , then GGG contains a triangle.
m>⌊n2/4⌋\boldsymbol{m > \lfloor n^2/4 \rfloor}m>⌊n2/4⌋ Sharp: K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}K⌊n/2⌋,⌈n/2⌉ has ⌊n2/4⌋\lfloor n^2/4 \rfloor⌊n2/4⌋ edges and no triangle (e.g. K2,3K_{2,3}K2,3 , K3,3K_{3,3}K3,3 ).
GGG has order nnn and contains no triangle. Why is deg⁡u+deg⁡v≤n\deg u + \deg v \le ndegu+degv≤n for every edge uvuvuv ?
Each of the other n−2n - 2n−2 vertices is adjacent to at most one of uuu and vvv . That gives at most n−2n - 2n−2 , plus 1 each for uuu and vvv being adjacent to each other.
Mantel: every graph of order n≥3n \ge 3n≥3 and size m>⌊n2/4⌋m > \lfloor n^2/4 \rfloorm>⌊n2/4⌋ contains a triangle.How does the proof go, taking a smallest counterexample GGG (order nnn , size ⌊n2/4⌋+1\lfloor n^2/4 \rfloor + 1⌊n2/4⌋+1 , no triangle)?
Delete both ends of an edge uvuvuv : H=G−u−vH = G - u - vH=G−u−v is a smaller counterexample. No triangle gives deg⁡u+deg⁡v≤n\deg u + \deg v \le ndegu+degv≤n , so HHH (order n−2n - 2n−2 ) has at least ⌊n2/4⌋+1−(n−1)=⌊(n−2)2/4⌋+1\lfloor n^2/4 \rfloor + 1 - (n - 1) = \lfloor (n-2)^2/4 \rfloor + 1⌊n2/4⌋+1−(n−1)=⌊(n−2)2/4⌋+1 edges and still no triangle.
Theorem 11.11 For every integer k≥2k \ge 2k≥2 , the only graph of order 2k2k2k and size k2k^2k2 that contains no triangle is … ?
Kk,k\boldsymbol{K_{k,k}}Kk,k
For k≥2k \ge 2k≥2 , the only triangle-free graph of order 2k2k2k and size k2k^2k2 is Kk,kK_{k,k}Kk,k .In a smallest counterexample GGG , what does deleting the ends of an edge uvuvuv give, and how does it finish the proof?
H=G−u−vH = G - u - vH=G−u−v has ≥(k−1)2\ge (k-1)^2≥(k−1)2 edges, so by Mantel exactly (k−1)2(k-1)^2(k−1)2 , and by minimality H=Kk−1,k−1H = K_{k-1,k-1}H=Kk−1,k−1 . At most 2k−22k - 22k−2 edges touch uuu or vvv besides uvuvuv , hence k2−(2k−1)k^2 - (2k - 1)k2−(2k−1) edges remain. Exactly 2k−22k - 22k−2 means every vertex of HHH is adjacent to exactly one of u,vu, vu,v ; uuu 's neighbors lie in one partite set (else a triangle), vvv 's in the other, so G=Kk,kG = K_{k,k}G=Kk,k .
Corollary 11.14 GGG is a graph of order n≥3n \ge 3n≥3 . Which sizes of GGG force a triangle?
Size ≥⌊n2/4⌋+1\ge \lfloor n^2/4 \rfloor + 1≥⌊n2/4⌋+1 , or size ⌊n2/4⌋\lfloor n^2/4 \rfloor⌊n2/4⌋ with G≠K⌊n/2⌋,⌈n/2⌉G \ne K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}G=K⌊n/2⌋,⌈n/2⌉ . Order 2k2k2k : size k2k^2k2 and G≠Kk,kG \ne K_{k,k}G=Kk,k . Order 2k+12k + 12k+1 : size k2+kk^2 + kk2+k and G≠Kk,k+1G \ne K_{k,k+1}G=Kk,k+1 .
What is the maximum size of a triangle-free graph of order 7, and which graphs attain it?
12, attained only by K3,4K_{3,4}K3,4 . ⌊49/4⌋=12\lfloor 49/4 \rfloor = 12⌊49/4⌋=12 : size 13 forces a triangle, and so does size 12 unless G=K3,4G = K_{3,4}G=K3,4 .
What question did Paul Turán ask, and how did he come to it?
What is the maximum size of a graph of order nnn that contains no KkK_kKk ? It came from a 1940 letter from Szekeres. Turán solved it in a World War II labor camp, with no paper to work on. Mantel's theorem is the triangle case.
Turán's work on the maximum size of graphs without a given complete subgraph led to the creation of extremal graph theory.
V1⊆V(G)V_1 \subseteq V(G)V1⊆V(G) . G[V1]G[V_1]G[V1] has m1m_1m1 edges, and m2m_2m2 edges join V1V_1V1 to V(G)−V1V(G) - V_1V(G)−V1 . ∑v∈V1deg⁡Gv= ?\displaystyle\sum_{v \in V_1} \deg_G v = \; ?v∈V1∑degGv=?
2m1+m2\boldsymbol{2m_1 + m_2}2m1+m2 Edges inside V1V_1V1 are counted twice, edges leaving V1V_1V1 once.
Theorem 11.15 Let 2≤k<n2 \le k < n2≤k<n . Among all graphs of order nnn that do not contain Kk+1K_{k+1}Kk+1 , at least one of maximum size is … ?
A kkk -partite graph.
Among graphs of order nnn without Kk+1K_{k+1}Kk+1 , some graph of maximum size mmm is kkk -partite (proof by induction on kkk ).Starting from such a graph GGG and a vertex vvv of maximum degree Δ\DeltaΔ , which kkk -partite graph HHH does the proof build?
H=F′+K‾n−Δ\boldsymbol{H = F' + \overline{K}_{n-\Delta}}H=F′+Kn−Δ : F′F'F′ is a (k−1)(k-1)(k−1) -partite graph of maximum size among KkK_kKk -free graphs of order Δ\DeltaΔ (it exists by induction), joined to n−Δn - \Deltan−Δ independent vertices. F=G[N(v)]F = G[N(v)]F=G[N(v)] has no KkK_kKk (else vvv gives a Kk+1K_{k+1}Kk+1 ), so its size s≤s′s \le s's≤s′ , the size of F′F'F′ . Every edge of GGG lies in FFF or has an end among the n−Δn - \Deltan−Δ vertices outside FFF , e…
What is the Turán graph Tn,kT_{n,k}Tn,k ?
The complete kkk -partite graph of order nnn whose partite sets differ in size by at most 1. Each partite set has ⌊n/k⌋\lfloor n/k \rfloor⌊n/k⌋ or ⌈n/k⌉\lceil n/k \rceil⌈n/k⌉ vertices; if k∤nk \nmid nk∤n with remainder rrr , exactly rrr sets have ⌈n/k⌉\lceil n/k \rceil⌈n/k⌉ .
What are the partite set sizes of the Turán graphs T11,3T_{11,3}T11,3 and T14,6T_{14,6}T14,6 (complete multipartite, set sizes differing by at most 1)?
T11,3T_{11,3}T11,3 : 3, 4, 4. T14,6\ T_{14,6} T14,6 : 2, 2, 2, 2, 3, 3.
Theorem 11.16 Let 1≤k≤n1 \le k \le n1≤k≤n and n≥3n \ge 3n≥3 . Among all kkk -partite graphs of order nnn , which has maximum size?
The Turán graph Tn,kT_{n,k}Tn,k , and it is the unique one.
A complete kkk -partite graph has partite sets of sizes n1≤⋯≤nkn_1 \le \dots \le n_kn1≤⋯≤nk with nk−n1≥2n_k - n_1 \ge 2nk−n1≥2 . Why isn't it of maximum size among kkk -partite graphs of the same order?
Moving a vertex from the largest set to the smallest loses n1n_1n1 edges and gains nk−1>n1n_k - 1 > n_1nk−1>n1 . So a maximum one has nk−n1≤1n_k - n_1 \le 1nk−n1≤1 , i.e. it is the Turán graph Tn,kT_{n,k}Tn,k .
Turán's Theorem Let 2≤k<n2 \le k < n2≤k<n . Among all graphs of order n≥3n \ge 3n≥3 that do not contain Kk+1K_{k+1}Kk+1 , which has maximum size?
The Turán graph Tn,kT_{n,k}Tn,k , uniquely. Tn,kT_{n,k}Tn,k : complete kkk -partite, partite set sizes differing by at most 1. For k=2k = 2k=2 , Tn,2=K⌊n/2⌋,⌈n/2⌉T_{n,2} = K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}Tn,2=K⌊n/2⌋,⌈n/2⌉ : Mantel's theorem.
What is the maximum size of a graph of order 11 that contains no K4K_4K4 ?
40\boldsymbol{40}40 By Turán's Theorem, T11,3T_{11,3}T11,3 with partite sets of sizes 3, 4, 4: 3⋅4+3⋅4+4⋅4=403 \cdot 4 + 3 \cdot 4 + 4 \cdot 4 = 403⋅4+3⋅4+4⋅4=40 .
Theorem 11.18 Every graph of order n≥3n \ge 3n≥3 and size at least … ? is Hamiltonian.
(n−12)+2\boldsymbol{\binom{n-1}{2} + 2}(2n−1)+2 Sharp: Kn−1K_{n-1}Kn−1 plus a pendant edge has (n−12)+1\binom{n-1}{2} + 1(2n−1)+1 edges and is not Hamiltonian. G1G_1G1 (order 4, size 4) and G3G_3G3 (order 5, size 7) are not Hamiltonian; G2G_2G2 , the only graph of order 4 and size 5, is.
Ore: if deg⁡u+deg⁡v≥n\deg u + \deg v \ge ndegu+degv≥n for every two nonadjacent vertices u,vu, vu,v of a graph GGG of order n≥3n \ge 3n≥3 , then GGG is Hamiltonian.Why does a graph of order nnn and size (n−12)+2\binom{n-1}{2} + 2(2n−1)+2 satisfy this condition?
For nonadjacent u,vu, vu,v , G−u−vG - u - vG−u−v has (n−12)+2−deg⁡u−deg⁡v\binom{n-1}{2} + 2 - \deg u - \deg v(2n−1)+2−degu−degv edges, at most (n−22)\binom{n-2}{2}(2n−2) . So deg⁡u+deg⁡v≥(n−12)−(n−22)+2=(n−2)+2=n\deg u + \deg v \ge \binom{n-1}{2} - \binom{n-2}{2} + 2 = (n - 2) + 2 = ndegu+degv≥(2n−1)−(2n−2)+2=(n−2)+2=n .
For graphs FFF and HHH , what is the monochromatic Ramsey number mr(F,H)mr(F, H)mr(F,H) ?
The smallest nnn such that every coloring of the edges of KnK_nKn with two colors gives a monochromatic FFF or a monochromatic HHH . Monochromatic: all edges the same color, either color. So mr(F,H)=mr(H,F)≤r(F,H)mr(F, H) = mr(H, F) \le r(F, H)mr(F,H)=mr(H,F)≤r(F,H) .
When does the monochromatic Ramsey number mr(F,H)mr(F, H)mr(F,H) (2-colored KnK_nKn forces a monochromatic FFF or HHH ) reduce to an ordinary Ramsey number?
If F≅HF \cong HF≅H : mr(F,H)=r(F,H)mr(F, H) = r(F, H)mr(F,H)=r(F,H) . If F⊆HF \subseteq HF⊆H : mr(F,H)=r(F,F)mr(F, H) = r(F, F)mr(F,H)=r(F,F) . A monochromatic HHH contains a monochromatic FFF .
r(K3,K1,3)=7r(K_3, K_{1,3}) = 7r(K3,K1,3)=7 .What is the monochromatic Ramsey number mr(K3,K1,3)mr(K_3, K_{1,3})mr(K3,K1,3) (2-colored KnK_nKn forces a monochromatic K3K_3K3 or K1,3K_{1,3}K1,3 )?
6\boldsymbol{6}6 ≤6\le 6≤6 : every red-blue K6K_6K6 has a monochromatic K3K_3K3 , since r(K3,K3)=6r(K_3, K_3) = 6r(K3,K3)=6 . ≥6\ge 6≥6 : K5K_5K5 with a red C5C_5C5 and a blue C5C_5C5 has no monochromatic K3K_3K3 and no vertex with 3 edges of one color.
The vertices of KnK_nKn are distinct positive integers. When is an edge coloring of KnK_nKn a minimum coloring, and when a maximum coloring?
Minimum: edges ijijij and kℓk\ellkℓ have the same color iff min⁡{i,j}=min⁡{k,ℓ}\min\{i, j\} = \min\{k, \ell\}min{i,j}=min{k,ℓ} . Maximum: iff max⁡{i,j}=max⁡{k,ℓ}\max\{i, j\} = \max\{k, \ell\}max{i,j}=max{k,ℓ} .
A subgraph whose edges all have different colors is called a rainbow subgraph.
Each of the four triangles of this edge-colored K5K_5K5 (vertex numbers beside the vertices, colors on the edges) is monochromatic, rainbow, minimum-colored or maximum-colored. Which is which, left to right?
Monochromatic, rainbow, minimum coloring, maximum coloring. Triangle 2,3,42, 3, 42,3,4 : edges 232323 and 242424 (min 2) both have color 4, edge 343434 has 6. Triangle 3,4,53, 4, 53,4,5 : edges 353535 and 454545 (max 5) both have 7, edge 343434 has 6.
Theorem 11.20 (Erdős and Rado) For every positive integer kkk there is an nnn such that if each edge of KnK_nKn (vertex set {1,…,n}\{1, \dots, n\}{1,…,n} ) is colored with a positive integer, then … ?
Some complete subgraph of order kkk is monochromatic, rainbow, minimum-colored or maximum-colored. Any number of colors may be used.
For a nonempty graph FFF , what is the rainbow Ramsey number RR(F)RR(F)RR(F) ?
The smallest nnn such that every edge coloring of KnK_nKn , with any number of colors, gives a monochromatic FFF or a rainbow FFF . Defined by Arie Bialostocki and William Voxman. It does not exist for all FFF .
Theorem 11.21 Let FFF be a graph without isolated vertices. When is the rainbow Ramsey number RR(F)RR(F)RR(F) (any coloring of KnK_nKn gives a monochromatic or rainbow FFF ) defined?
Exactly when FFF is a forest.
Why is the rainbow Ramsey number RR(F)RR(F)RR(F) (any coloring of KnK_nKn gives a monochromatic or rainbow FFF ) undefined when FFF contains a cycle?
In the minimum coloring of KnK_nKn (edge ijijij colored min⁡{i,j}\min\{i, j\}min{i,j} ), no cycle is monochromatic or rainbow. On a cycle (v1,…,vk,v1)(v_1, \dots, v_k, v_1)(v1,…,vk,v1) with smallest vertex v1v_1v1 : v1v2v_1v_2v1v2 and v1vkv_1v_kv1vk both get color v1v_1v1 (not rainbow), while v2v3v_2v_3v2v3 does not (not monochromatic).
In a minimum coloring of KkK_kKk on vertices v1<v2<⋯<vkv_1 < v_2 < \dots < v_kv1<v2<⋯<vk , edge vivjv_iv_jvivj has color min⁡{vi,vj}\min\{v_i, v_j\}min{vi,vj} .Why does such a KkK_kKk contain a rainbow copy of every forest of order kkk ?
Extend the forest to a tree TTT with a root rrr , and label TTT 's vertices so that farther from rrr means smaller ( r=vkr = v_kr=vk ). Each edge then gets the color of its endpoint farther from rrr , and every non-root vertex is that endpoint for exactly one edge: colors v1,…,vk−1v_1, \dots, v_{k-1}v1,…,vk−1 , all different. k=8k = 8k=8 , root v8v_8v8 .
RR(K1,3)= ?RR(K_{1,3}) = \; ?RR(K1,3)=? (smallest nnn such that every coloring of KnK_nKn gives a monochromatic or a rainbow K1,3K_{1,3}K1,3 )
6\boldsymbol{6}6 ≤6\le 6≤6 : without a monochromatic K1,3K_{1,3}K1,3 , each color appears at most twice at a vertex, so the 5 edges at a vertex of K6K_6K6 use 3 colors: a rainbow K1,3K_{1,3}K1,3 . ≥6\ge 6≥6 : K5K_5K5 with a red C5C_5C5 and a blue C5C_5C5 (2 edges of each color at each vertex).
For nonempty graphs F1,F2F_1, F_2F1,F2 , what is the rainbow Ramsey number RR(F1,F2)RR(F_1, F_2)RR(F1,F2) ?
The smallest nnn such that every edge coloring of KnK_nKn , with any number of colors, gives a monochromatic F1F_1F1 or a rainbow F2F_2F2 . As for Ramsey numbers, RR(F1,F2)≥max⁡{n1,n2}RR(F_1, F_2) \ge \max\{n_1, n_2\}RR(F1,F2)≥max{n1,n2} , where n1,n2n_1, n_2n1,n2 are the orders.
Theorem 11.23 (from a result of Erdős and Rado) F1,F2F_1, F_2F1,F2 have no isolated vertices. When does RR(F1,F2)RR(F_1, F_2)RR(F1,F2) exist (every coloring of KnK_nKn gives a monochromatic F1F_1F1 or a rainbow F2F_2F2 )?
If and only if F1F_1F1 is a star or F2F_2F2 is a forest. So RR(K3,K3)RR(K_3, K_3)RR(K3,K3) does not exist.
Why does no minimum coloring of KnK_nKn (edge ijijij colored min⁡{i,j}\min\{i, j\}min{i,j} ) contain a monochromatic F1F_1F1 or a rainbow F2F_2F2 when F1F_1F1 is not a star and F2F_2F2 is not a forest?
Every color class is a star (all edges of color iii contain vertex iii ), and no cycle is rainbow. So RR(F1,F2)RR(F_1, F_2)RR(F1,F2) (any coloring of KnK_nKn gives a monochromatic F1F_1F1 or a rainbow F2F_2F2 ) does not exist for such F1,F2F_1, F_2F1,F2 .
RR(F,P3)= ?RR(F, P_3) = \; ?RR(F,P3)=? (smallest nnn such that every coloring of KnK_nKn gives a monochromatic FFF or a rainbow P3P_3P3 )
4\boldsymbol{4}4 ≥4\ge 4≥4 since FFF has order 4. ≤4\le 4≤4 : with no rainbow P3P_3P3 , any two adjacent edges of K4K_4K4 have the same color, so all edges do: a monochromatic FFF .
RR(P3,F)= ?RR(P_3, F) = \; ?RR(P3,F)=? (smallest nnn such that every coloring of KnK_nKn gives a monochromatic P3P_3P3 or a rainbow FFF )
5\boldsymbol{5}5 , while RR(F,P3)=4RR(F, P_3) = 4RR(F,P3)=4 : unlike Ramsey numbers, RRRRRR is not symmetric. ≥5\ge 5≥5 : color the three perfect matchings of K4K_4K4 with 1, 2, 3. No monochromatic P3P_3P3 , and a rainbow FFF would need 4 colors.
Why does every edge coloring of K5K_5K5 give a monochromatic P3P_3P3 or a rainbow FFF ?
Without a monochromatic P3P_3P3 , the 4 edges at a vertex vvv have 4 colors, and v1v2v_1v_2v1v2 has neither color 1 nor 2: triangle vv1v2vv_1v_2vv1v2 plus vv3vv_3vv3 or vv4vv_4vv4 is a rainbow FFF . vvivv_ivvi colored iii . Use vv3vv_3vv3 unless v1v2v_1v_2v1v2 has color 3, then vv4vv_4vv4 .
F1,F2F_1, F_2F1,F2 have no isolated vertices, F2F_2F2 has size mmm , and k≥mk \ge mk≥m . What is the kkk -rainbow Ramsey number RRk(F1,F2)RR_k(F_1, F_2)RRk(F1,F2) ?
The smallest nnn such that every coloring of the edges of KnK_nKn from {1,…,k}\{1, \dots, k\}{1,…,k} gives a monochromatic F1F_1F1 or a rainbow F2F_2F2 . It always exists, e.g. RRk(K3,K3)RR_k(K_3, K_3)RRk(K3,K3) for k≥3k \ge 3k≥3 , although RR(K3,K3)RR(K_3, K_3)RR(K3,K3) doesn't. k≥mk \ge mk≥m is needed because a rainbow F2F_2F2 uses mmm colors.
Which connected graphs contain no 2K22K_22K2 (two nonadjacent edges)?
Stars and K3K_3K3 . Every two edges are adjacent.
RR3(2K2,K3)= ?RR_3(2K_2, K_3) = \; ?RR3(2K2,K3)=? (smallest nnn such that every coloring of KnK_nKn with colors 1, 2, 3 gives a monochromatic 2K22K_22K2 or a rainbow K3K_3K3 )
6\boldsymbol{6}6 ≥6\ge 6≥6 : red star at v1v_1v1 , blue triangle, green star. A rainbow K3K_3K3 needs a red edge, so contains v1v_1v1 , but both its edges at v1v_1v1 are red.
Why does every coloring of K6K_6K6 with 3 colors give a monochromatic 2K22K_22K2 (two nonadjacent edges of the same color)?
Otherwise every color class would be a star K1,5K_{1,5}K1,5 , and two such stars share an edge. Some color has ≥5\ge 5≥5 of the 15 edges. Pairwise adjacent edges form a star or K3K_3K3 , and a star in K6K_6K6 has ≤5\le 5≤5 edges, so each color has exactly 5 edges at one vertex. Red at vvv , blue at uuu : edge uvuvuv would be both.
Who was Paul Erdős (1913–1996)?
A Hungarian mathematician with about 1500 papers and more than 500 co-authors, the most papers of any mathematician. Born in Budapest; for most of his life he had no job and no home, traveling from one mathematician to the next. He died at a graph theory workshop in Warsaw.
What did Erdős and Selberg prove in 1949?
Elementary proofs (without complex analysis) of the Prime Number Theorem π(n)∼n/ln⁡n\pi(n) \sim n / \ln nπ(n)∼n/lnn . Conjectured by Gauss, first proved in 1896 by Hadamard and de la Vallée Poussin. Earlier, Erdős gave an elegant proof that there is a prime between nnn and 2n2n2n .
What is a mathematician's Erdős number?
The distance from that mathematician to Erdős in the collaboration graph. Collaboration graph: vertices are mathematicians, adjacent if they co-authored a paper. Erdős has number 0, his co-authors 1, and so on.
What is Albert Einstein's Erdős number, and why?
2: he wrote a paper with Ernst Straus, who wrote one with Erdős, but never wrote one with Erdős himself.
What is an actor's Kevin Bacon number?
The distance to Kevin Bacon in the graph of actors, adjacent when they appeared in the same feature movie. E.g. Cary Grant has 2: he appeared with Walter Matthau in Charade, and Matthau with Bacon in JFK.
Where does the phrase “six degrees of separation” come from?
Stanley Milgram's 1967 experiment tracking chains of acquaintances in the US. He claimed that on average two people are joined by a path of length 6. Erdős numbers and Kevin Bacon numbers go back to this.
What is a person's Erdős–Bacon number?
Erdős number + Kevin Bacon number. Physicist Brian Greene: Erdős number 3 (paper with Yau, who wrote one with Graham, a co-author of Erdős), Bacon number 2 (via John Di Benedetto), so Erdős–Bacon number 5.
Which mathematician with Erdős number 1 supported himself as a circus performer and became president of the International Jugglers' Association?
Ronald Graham. He worked 37 years at Bell Laboratories and was president of both the AMS and the MAA.