WYKŁAD 3.
Kliki i zbiory niezależne
• Ile
co najmniej
krawędzi gwarantuje
istnienie kliki wielkości k?
• Ile
co najwyżej
krawędzi gwarantuje
istnienie zbioru niezależnego
wielkości k?
• Ile
co najmniej
wierzchołków
gwarantuje klikę wielkości k
lub
zbiór niezależny wielkości l ?
Ile krawędzi gwarantuje
K_3 ?
• n^2/4
nie gwarantuje, bo K(n/2,n/2)
• Tw. (Mantel, 1907)
Jeśli graf o
n
wierzchołkach ma więcej niż
n^2/4
krawędzi, to zawiera trójkąt.
• Dowód:
G – graf bez trójkąta, v
--wierzchołek o stopniu Δ, N(v) –
zbiór sąsiadów v w G. Zbiór N(v)
jest niezależny, stąd
4
)
(
2
/
n
n
e(G)
Ilustracja dowodu Tw.
Mantla
v
N(v)
n-Δ-1
Δ
V-{v}-N(v)
Wniosek z dowodu Tw.
Mantla
• Jeśli n jest parzyste, G ma n^2/4 krawędzi
i nie zawiera K_3, to G=K(n/2,n/2).
• Jeśli n jest nieparzyste, G ma (n^2-1)/4
krawędzi i nie zawiera K_3, to G=K((n-
1)/2,(n+1)/2).
• Dowód dla n parzystego
: w dowodzie Tw.
Mantla równość e(G)=n^2/4 zachodzi
tylko, gdy Δ=n/2 i nie ma krawędzi o obu
końcach w V-N(v).
Uogólnienie problemu
• Dane: graf H i liczba naturalna n;
• Graf G nie zawierający H, o n
wierzchołkach i
największej
możliwej
liczbie krawędzi nazywamy
ekstremalnym
dla H i n, a jego liczbę krawędzi oznaczamy
przez
ex(n,H).
• Na przykład, dla n parzystego i H=K_3,
K(n/2,n/2)
jest ekstremalny, a
ex(n,K_3)=n^2/4.
Tw. Turána -- intuicja
Żeby upchnąć jak najwięcej krawędzi
unikając K_{k+1}, trzeba budować
k-dzielny graf pełny.
n/k
n/k
n/k
Tw. Turána
Graf Turána
T_k(n)
to k-dzielny graf pełny, którego podział
wierzchołków składa się z k-r zbiorów mocy q i r zbiorów
mocy q+1. Dla n=1,...,k-1 przyjmujemy
T_k(n)
= K_n.
Oznaczmy
t_k(n)
=e(T_k(n)). Jasne, że
k
r
r,
qk
n, n
k
0
Tw.Turána 1941
Jedynym grafem
ekstremalnym dla K_{k+1} i n jest graf
Turána T_k(n). W szczególności
t_k(n)
})
ex(n,K_{k
1
t_k(n)
})
ex(n,K_{k
1
Dowód Tw. Turána
• Indukcja względem n: prawda dla
n=1,...,k.
• Załóżmy, że n>k a G jest grafem
ekstremalnym dla n i K_{k+1}.
• G musi zawierać klikę K={x_1,...,x_k}
mocy k.
• Z zał.ind. e(G-K) nie przekracza t_k(n-k).
• Każdy wierzchołek grafu G-K ma w K co
najwyżej k-1 sąsiadów.
n
t
k
k
k
n
k
n
t
G
e
k
k
2
)
1
)(
(
)
(
Ilustracja: k=4
K
G-K
Ilustracja: grafy Turána
n=13, k=4, t_k(13)-t_k(9)=
6
+
9•3
Dowód Tw. Turána – c.d.
• G jest ekstremalny, więc e(G)=t_k(n).
• Zatem każdy wierzchołek w G-K ma
dokładnie
k-1 sąsiadów w K.
• Niech V_i={v: vx_i nie jest
krawędzią}.
• Zbiory V_i są niezależne i pokrywają V,
więc G jest k-dzielny.
• Ale jedynym ekstremalnym grafem k-
dzielnym jest graf Turána T_k(n).
Oszacowania liczb Turána
• Łatwo pokazać, że (
ćwiczenia
)
2
2
1
n
k
k
n
t
k
k
k
n
n
t
k
n
1
2
lim
1
Ile krawędzi gwarantuje
α>2 ?
nie gwarantuje, bo
2K_{n/2}
(tutaj n
parzyste)
czyli dopełnienie grafu Turána.
Ale mniej już tak – na podstawie Tw. Turána.
2
2
/
2
n
Oszacowanie α z dołu
• Tw. Caro’79 i Wei’81
V
v
v
d
G
1
1
Dowód
: Dla każdej permutacji
wierzchołków π, niech l(π) będzie
liczbą wierzchołków mających
wszystkich sąsiadów „na prawo”.
Tworzą one zbiór niezależny, więc
l
G
Dowód – c.d.
• Niech ł(v) będzie liczbą permutacji, w
których v ma wszystkich sąsiadów na prawo.
Wtedy
v
v
ł
l
• oraz
1
!
)!
1
(
!
1
v
v
v
v
d
n
d
n
d
d
n
v
ł
• Zatem istnieje π takie, że
V
v
v
d
l
1
1
Ilustracja
v
N(v)
Przyjęcie na 6 osób
• Wśród dowolnych trzech osób
zawsze
są co najmniej dwie tej samej płci.
• Wśród dowolnych sześciu osób
zawsze
są co najmniej trzy, które się
znają
LUB
co najmniej trzy, które się
nie znają.
A
B
C
D
E
F
Liczba K_3 łącznie w
grafie i jego dopełnieniu
Goodman 1959
Łącznie trójkątów w grafie
na n wierzchołkach i jego dopełnieniu
jest co najmniej n(n-1)(n-5)/24.
Dowód
: Niech t_i będzie liczbą
indukowanych podgrafów grafu G o 3
wierzchołkach i i krawędziach, i=0,1,2,3.
2
1
2
1
t
t
d
n
d
v
V
v
v
Ilustracja
v
d_v
n-1- d_v
Dowód tw. Goodmana --
dokończenie
2
2
1
3
0
2
1
2
3
)
(
3
n
n
n
t
t
n
t
t
Tw. Ramseya
Notacja „strzałkowa” Erdősa-Rado
:
Piszemy n
(k,l), gdy każdy graf na n
wierzchołkach zawiera klikę mocy k
LUB
zbiór niezależny mocy l (równoważnie,
jego dopełnienie zawiera klikę mocy l).
Przykład: 6
(3,3)
Tw. (Ramsey 1930)
Dla wszystkich
naturalnych k i l, istnieje n takie, że
n
(k,l).
Dowód tw. Ramseya
• Indukcja względem k+l
• Jeśli k=2 to l
(k,l).
• Zawsze: n
(k,l) wgdy n
(l,k)
• Weźmy k>2 i l>2; niech n_1
(k-1,l),
n_2
(k,l-1) (
tutaj stosujemy zał.
ind
.)
• Pokażemy, że n_1+n_2
(k,l).
• W dowolnym grafie G na n_1+n_2
wierzchołkach, każdy wierzchołek v
ma albo co najmniej n_1 sąsiadów
albo co najmniej n_2 nie-sąsiadów.
Dowód tw. Ramseya – c.d.
• Bez straty ogólności (symetria!) przyjmijmy
przypadek pierwszy i do podgrafu
indukowanego G[N(v)], gdzie |N(v)|=n_1,
zastosujmy własność n_1
(k-1,l).
• Jeśli G[N(v)] zawiera zbiór niezależny mocy
l, to koniec dowodu.
• Jeśli G[N(v)] zawiera klikę mocy k-1, to ta
klika wraz z wierzchołkiem v tworzy klikę
mocy k.
Ilustracja
v
n_1=R(k-1,l)
n_2=R(k,l-1)
Liczby Ramseya
• R(k,l) to najmniejsza liczba n taka, że n
(k,l).
• R(3,3)=6 bo 6
(3,3) oraz istnieje graf na 5
wierzchołkach (
jaki?
) taki, że ω=α=2.
• Z dowodu Tw. Ramseya wynika rekurencja
)
1
,
(
)
,
1
(
)
,
(
l
k
R
l
k
R
l
k
R
10
4
6
)
2
,
4
(
)
3
,
3
(
)
3
,
4
(
R
R
R
9
3
4
)
,
R(
18
)
4
,
3
(
2
)
4
,
4
(
R
R
9
)
4
,
3
(
R
18
)
4
,
4
(
R
?
)
5
,
5
(
R
Oszacowania liczb
Ramseya
k
c
k
k
k
k
R
k
4
1
2
2
)
,
(
2
/
2
)
,
(
k
k
k
R
(1)
(2)
Gra ramseyowska -- online
Opis gry
: Zaczynając od pustego grafu, w
każdej rundzie
Konstruktor
rysuje krawędź
a
Malarz
maluje ją jednym z dwóch kolorów.
Malarz
przegrywa, gdy pojawi się
monochromatyczny trójkąt.
Ile rund może przetrwać
Malarz
, zakładając,
że obaj gracze grają bezbłędnie?
Na pewno nie więcej niż 15 (
dlaczego
?), ale
czy
Konstruktor
może osiągnąć wygraną
wcześniej?
Przykład gry