- 1. feladat F M
(a) Egy
x
pont vagy szomszédos legalább
k
+
l
−
1
k
−
1
ponttal, vagy nem szomszédos legalább
k
+
l
−
1
k
ponttal. (b)
R
2
(
a
1
,
a
2
)
létezése az előző eredményből
következik. Alkalmazzunk indukciót
k
-ra.
- 2. feladat F M
(a)
[
e
k
!
]
=
k
[
e
(
k
−
1
)
!
]
+
1
. (b) A felső korlát 14.1a-ból
triviális. Az alsó korlát bizonyításához tekintsük azt
a
H
hipergráfot, melyre
V
(
H
)
=
E
(
K
n
)
és
E
(
H
)
=
{
E
(
A
)
:
A
k
pontú teljes részgráfja
K
n
-nek
}
.
- 3. feladat F M
(a)
r
=
2
-re ezt már tudjuk. Alkalmazzunk
indukciót (
a
1
+
…
+
a
k
)-ra és
r
-re. (b) Válasszunk az elemek egy
olyan rendezett
(
x
1
,
…
,
x
m
)
halmazát, melyre az indexek minden
1
≤
ν
1
<
…
<
ν
r
<
m
r
-esére minden
(
r
+
1
)
elemű,
(
x
ν
1
,
…
,
x
ν
r
,
x
μ
)
(
ν
r
<
μ
≤
m
)
alakú halmaz színe azonos.
- 4. feladat F M
Könnyű
n
-re alkalmazott indukcióval.
- 5. feladat F M
Tekintsünk egy
P
maximális piros utat és két
Q
1
,
Q
2
diszjunkt kék utat, melyekre
Q
1
és
Q
2
(
(
V
(
P
)
,
V
(
G
)
−
V
(
P
)
)
)-élekből állnak, végpontjaik (
V
(
G
)
−
V
(
P
)
)-beliek, nem tartalmazzák
P
végpontjait, és hosszuk maximális.
Bizonyítsuk be, hogy
Q
1
∪
Q
2
∪
P
minden pontot lefed.
- 6. feladat F M
(a) Legyen
(
x
0
,
…
,
x
2
k
)
egy piros kör. Mutassuk meg, hogy
(
x
i
,
x
i
+
2
)
kék,
(
x
i
,
x
i
+
4
)
piros és
(
x
i
,
x
i
+
3
)
kék (
i
=
0
,
…
,
2
k
;
x
2
k
+
1
+
j
=
x
j
). (b) Legyen
(
x
1
,
…
,
x
2
k
)
piros kör. Mutassuk meg, hogy
{
x
1
,
x
3
,
…
,
x
2
k
−
1
}
és
{
x
2
,
x
4
,
…
,
x
2
k
}
teljes részgráfokat feszítenek. (c)
Mutassuk meg, hogy létezik monokromatikus
M
hosszú kör valamely
M
≥
m
-re, majd használjuk (a)-t és
(b)-t.
- 7. feladat F M
Tekintsük a 17. ábra konfigurációját, ahol minden
él hossza egységnyi.
- 8. feladat F M
Tekintsük hat 1,
a
és
b
oldalú háromszög 18. ábra szerinti
elrendezését.
- 9. feladat F M
(a) Vegyünk egy sávonkénti színezést. (b) Lásd a
19. ábrát.
- 10. feladat F M
(a) Tekintsük két nagy szimplex Descartes
szorzatát. (b) Feltehetjük, hogy
a
b
=
1
, ahol
a
,
b
az
R
két oldal-vektora. Színezzük a
w
pontot
⌊
w
2
⌋
modulo 4-gyel.
- 11. feladat F M
Legyen
{
A
1
,
…
,
A
k
}
az
{
1
,
…
,
n
}
szóban forgó partíciója. Tekintsük a
teljes gráfot
{
1
,
…
,
n
+
1
}
-en és színezzük meg az
(
i
,
j
)
élt a
ν
színnel, ha
|
i
−
j
|
∈
A
ν
.
- 12. feladat F M
Alkalmazzunk indukciót
r
-re: Keressük „hosszú” intervallumok
egy
I
1
,
…
,
I
r
sorozatát, melynek első tagjai
számtani sorozatot alkotnak, és melyek hasonlóan vannak
színezve.
- 13. feladat F M
Használjuk 14.2a-t a
14.11-hez hasonló
módon.
- 14. feladat F M
(a) Először válasszunk egy nagy
T
halmazt és
A
1
,
B
1
⊆
S
−
T
halmazokat,
A
1
∩
B
1
=
∅
, úgy, hogy minden
X
⊆
T
-re
A
1
∪
X
,
B
1
∪
X
és
A
1
∪
B
1
∪
X
színe azonos. (b) Legyen
t
nagy (a)-ban, és színezzük az
{
i
1
,
…
,
i
ν
}
⊆
{
1
,
…
,
t
}
részhalmazt
A
i
1
∪
…
∪
A
i
ν
színével.
- 15. feladat F M
Színezzük ki egy
n
elemű halmaz részhalmazait az
elemszámuknak megfelelő színnel.
- 16. feladat F M
(a)
n
1
(
k
,
m
)
=
k
-ra triviális. (b) Legyen
|
T
|
=
k
m
r
−
1
,
T
⊆
S
. Színezzük
T
−
S
minden
a
pontját az
(
α
(
a
−
d
)
:
d
∈
m
T
)
m
|
T
|
-essel.
- 17. feladat F M
14.16b ismételt alkalmazásával találunk olyan
diszjunkt, nem üres
X
1
′
,
…
,
X
t
′
⊆
S
halmazokat és olyan
b
m
-vektort az
S
−
X
1
′
−
…
−
X
t
′
pontjain, hogy minden
m
-vektor színe azonos az
m
-vektor színével. Ezek után
alkalmazzuk 14.14b-t.
- 18. feladat F M
Használjunk a 14.15-höz hasonló módszert.
- 19. feladat F M
Tegyük fel, hogy
{
1
,
…
,
N
}
-nek minden
N
-re van olyan
k
-színezése, hogy egyetlen részhalmaz
sem rendelkezik a
P
tulajdonsággal. Keressünk ilyen
összerakható
k
-színezéseket.
- 20. feladat F M
(a) Használjuk a következő észrevételt: ha
x
,
y
és
z
eleget tesz (a)-nak és
x
,
y
,
z
≡
0
vagy
i
(
mod
5
)
, akkor
x
,
y
,
z
≡
0
(
mod
5
)
(minden rögzített
1
≤
i
≤
4
-re).
(b) Alkalmazzunk indukciót
k
-ra és Van der Waerden tételét.
- 21. feladat F M
Fordítsuk le az előző megoldás (a) és (b) részét
az általános esetre.
- 22. feladat F M
Színezzük ki a pontokat véletlenszerűen és
használjuk 2.18-at annak biztosításához, hogy minden él
minden színnel érintkezzen.
- 23. feladat F M
(a) Ez speciális esete 14.17-nek. (b) Ha adva van
r
1
,
…
,
r
k
≥
0
, bizonyítsuk be, hogy létezik olyan
N
¯
(
k
;
r
1
,
…
,
r
k
;
q
−
1
)
szám, melyre ha
n
≥
N
¯
és a
G
F
(
q
)
fölötti
n
-dimeziós projektív tér pontjai
k
színnel vannak színezve, akkor mindig
létezik olyan
i
≤
k
, és olyan
r
i
-dimenziós altér, melynek minden
pontja
i
színű. Próbáljuk meg redukálni ezt az
affin esetre a „végtelen messze lévő” hipersík
elhagyásával.
- 24. feladat F M
Ha
r
=
q
prímhatvány, akkor megteszik egy
elegendően nagy dimenziójú
G
F
(
q
)
fölötti affin tér egyenesei. Egyébként
vegyünk egy
q
≥
r
prímhatványt és zsugorítsuk egy
q
-uniform példány éleit.
- 25. feladat F M
Minden
a
i
-hez nézzük a legnagyobb
a
i
-vel induló monoton növő
sorozatot.
- 26. feladat F M
(a) Legyen
t
(
x
)
az olyan
x
=
a
1
<
a
2
<
…
sorozatok maximális hossza, melyekre
f
(
a
1
)
≤
f
(
a
2
)
≤
…
Igazoljuk, hogy ha
t
(
x
)
≥
t
(
1
)
−
k
, akkor
f
(
x
)
≤
2
k
(
0
≤
k
≤
t
(
1
)
−
1
)
. (b) Álljon
f
(
n
−
1
)
darab monoton csökkenő részből.
- 27. feladat F M
(a) Jelölje
η
(
x
,
y
)
és
ϕ
(
x
,
y
)
a leghosszabb
(
x
,
y
)
∈
E
(
T
n
)
éllel induló monoton növő, illetve
csökkenő utak hosszát. Bármely
a
és
b
pontokra
(b) A korlát élességének bizonyításához
alkalmazzunk indukciót
p
-re és
q
-ra.
- 28. feladat F M
(a) Legyen
x
i
+
1
az
pontoktól különböző pont (
0
≤
i
≤
m
−
1
). (b) Bizonyítsuk (a) és (b) egy
közös általánosítását: létezik
S
-nek olyan
(
x
1
,
…
,
x
2
n
)
rendezése, melyben minden
1
≤
j
≤
n
-re
a
ν
legalább
(
n
−
j
)
2
j
értékére igaz. (c) Keressünk
f
-et a következő formában: Adott egy
ϕ
függvény, melyre
1
≤
ϕ
(
i
)
≤
i
, legyen
f
(
X
)
az
X
halmaz
ϕ
(
|
X
|
)
-edik eleme (
X
⊆
S
=
{
1
,
…
,
2
n
−
1
−
1
}
).
- 29. feladat F M
Irányítsunk minden két adott pont által alkotott
(
p
,
q
)
szakaszt fölfelé, és színezzük az
i
színnel, ha az
x
tengely pozitív részével alkotott
szöge
i
n
π
és
i
+
1
n
π
között van. Mi lehet az
i
színű szakaszok által alkotott
G
i
gráf kromatikus száma, ha nem
tartalmaz „majdnem egyenes” töröttvonalat?
- 30. feladat F M
(a) Rendeljük az
(
y
1
−
y
2
)
∕
(
x
1
−
x
2
)
értéket az
S
-en értelmezett teljes gráf
(
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
)
éléhez; irányítsuk ezt
(
x
1
,
y
1
)
-ből
(
x
2
,
y
2
)
-be, ha
x
1
<
x
2
, és alkalmazzuk 14.27-et. (b) Hajtsuk
végre a 14.27 konstrukciót az itt szereplő speciális
típusú turnamentekkel.
- 31. feladat F M
(a) Színezzük a pontok egy négyesét pirosra, ha
konvex négyszöget alkot, egyébként kékre; alkalmazzuk a
Ramsey tételt. (b) A felső korlát az előző feladatból
azonnal adódik. Az alsó korláthoz rakjunk össze alulról
konvex
(
i
+
2
)
-szöget és felülről konvex
(
m
−
i
)
-szöget nem tartalmazó
m
−
2
i
méretű halmazokat minden
i
=
0
,
…
,
m
−
2
-re.