- 1. feladat F M
Rendeljünk egy páros
G
gráfot
H
-hoz a következőképpen: Legyen
U
=
V
(
H
)
,
W
=
E
(
H
)
,
V
(
G
)
=
U
∪
W
, és akkor és csak akkor kössük össze
u
∈
U
-t
w
∈
W
-vel, ha
u
∈
w
.
- 2. feladat F M
(a) Ha
E
olyan él, hogy
H
′
=
(
H
−
{
E
}
)
∖
E
összefüggő (
∅
∉
E
(
H
)
) , akkor találhatunk olyan
F
-et, melynek megvan a kívánt
tulajdonsága. (b) Végezzünk indukciót, egy
E
élt elhagyva az (a) részben.
- 3. feladat F M
Tekintsünk egy
3
-nál hosszabb kört, és válasszunk két
pontot, melyek egymás után következnek a körön, de van
egy további pont, mely közöttük van a
P
út által meghatározott
rendezésben.
- 4. feladat F M
Másképpen teljesen kiegyensúlyozott!
- 5. feladat F M
Alkalmazzuk 7.4-et és
7.6-ot.
- 6. feladat F M
Egy ilyen reprezentánsrendszer akkor és csak
akkor létezik, ha a
H
-nak van reprezentánsrendszere, és
ugyanígy, ha a
hipergráfnak is van reprezentánsrendszere,
ahol
U
x
a
H
olyan éleinek a halmaza, amelyek
tartalmazzák
x
-et.
- 7. feladat F M
Reprezentáljuk ezt a helyzetet egy
folyamproblémával (párosítási probléma helyett).
- 8. feladat F M
(a) Az
E
0
△
F
(
F
∈
E
(
H
)
) halmazok különbözőek! (b) Legyen
x
∈
V
(
H
)
, és tekintsük a
H
∖
x
hipergráfot és
H
′
-t, ahol
(c) Tekintsük a
H
1
=
H
−
x
,
H
2
=
H
−
E
(
H
1
)
hipergráfokat.
- 9. feladat F M
Tekintsük a
H
1
=
H
−
x
,
H
¯
2
=
H
−
E
(
H
1
)
,
H
2
=
H
¯
2
∖
x
hipergráfokat, valamely
x
∈
V
(
H
)
-ra.
- 10. feladat F M
(a) Bizonyítsuk
k
szerinti indukcióval, hogy létezik egy
olyan
X
⊆
V
(
H
)
halmaz, melyre
|
X
|
=
k
és
H
X
-nek legalább
k
+
1
különböző éle van
(
1
≤
k
≤
n
−
1
)
. (b) Alkossunk egy gráfot, mely az
(a) rész második megoldásához hasonlít. Bizonyítsuk be,
hogy ez a gráf páros, és nem tartalmaz
Θ
-gráfot. (c) Legyen
H
1
=
H
∖
x
,
V
(
H
2
)
=
V
(
H
)
−
x
, és
E
(
H
2
)
=
{
E
∈
E
(
H
)
:
x
∉
E
,
E
∪
{
x
}
∈
E
(
H
)
}
. Bizonyítsuk be, hogy vagy
H
1
kielégíti a probléma feltételét
k
-val, vagy
H
2
elégíti ki (
k
−
1
)-gyel.
- 11. feladat F M
Tekintsük az
x
∈
V
-t tartalmazó éleket, és végezzünk
indukciót.
- 12. feladat F M
(a) Átlagoljuk az osztályokba tartozó élek számát
a
V
(
H
)
minden két osztályt tartalmazó
partíciójára. (b) Átlagoljunk most a
V
(
H
)
minden
r
színnel való színezésére.
- 13. feladat F M
Lássuk be, és használjuk a
egyenlőtlenséget, ahol
d
(
x
)
az
x
pont foka.
- 14. feladat F M
Tegyük fel indirekte, hogy
m
>
n
. Összegezzük a
egyenlőtlenségeket.
- 15. feladat F M
(a)
H
kielégíti az előző probléma
feltételeit. (b) Ha
a
1
,
…
,
a
m
az élek karakterisztikus vektorai,
akkor
a
i
a
j
=
λ
teljesül
i
≠
j
esetén.
- 16. feladat F M
Hányszor számoltunk egy adott elemet mindkét
oldalon?
- 17. feladat F M
(a) Tegyük fel, hogy
x
∈
F
1
,
…
,
F
d
,
x
∉
F
d
+
1
,
…
,
F
m
. Vegyük
F
1
−
{
x
}
,
…
,
F
d
−
{
x
}
-et
m
−
d
-szer,
F
d
+
1
,
…
,
F
m
-et
d
-szer és alkalmazzuk 13.16-ot. (b)
Tegyük fel, hogy
|
F
1
|
=
…
=
|
F
m
−
1
|
=
2
k
,
F
m
=
∅
, és (indirekte)
m
=
k
2
+
k
+
3
. Lássuk be, hogy nincs több, mint
k
point, melynek a foka legalább
m
−
k
−
1
, de minden
F
j
-nek (
1
≤
j
≤
m
−
1
) legalább
k
+
1
ilyen pontot kell tartalmaznia.
- 18. feladat F M
(a) Legfeljebb az
X
és
E
(
H
)
−
X
egyike lehet él. (b) Használjuk
13.8b-t,
13.9-t, vagy
13.11-et.
- 19. feladat F M
Számoljuk le az olyan
(
E
1
,
E
2
)
élpárokat, melyekre
E
2
⊂
E
1
és nincs olyan
F
∈
E
(
H
)
, melyre
E
2
⊂
F
⊂
E
1
teljesül.
- 20. feladat F M
Használjunk
n
szerinti indukciót.
- 21. feladat F M
(a) Tekintsük a láncokat, melyeket az előző
problémában konstruáltunk. Egy másik bizonyítás;
számoljuk le a
V
(
H
)
azon permutációit, melyek egy
H
élt, mint kezdő szeletet tartalmaznak.
(b) A páros eset könnyű. Ha
n
=
2
k
+
1
, mutassuk meg, hogy minden él vagy
k
, vagy
k
+
1
méretű kell, hogy legyen, és hogy ha
X
⊂
Y
,
|
X
|
=
k
,
|
Y
|
=
k
+
1
teljesül, akkor
X
és
Y
egyike benne kell, hogy legyen
E
(
H
)
-ban.
- 22. feladat F M
Ha
A
és
B
maximális antiláncok, akkor
A
∨
B
=
{
x
∈
A
∪
B
:
x
≮
y
minden
y
∈
A
∪
B
-
r
e
}
egy maximális antilánc (ahol
x
<
y
azt jelenti, hogy
x
≤
y
és
x
≠
y
).
- 23. feladat F M
(b) bizonyításához tekintsük azon
S
E
(
E
∈
E
(
H
)
) részhalmazokat, melyek csak egy
E
éllel hasonlíthatóak össze, és
megfelelően választva egy Sperner rendszert
alkotnak.
- 24. feladat F M
Legyen
a
k
legnagyobb binomiális együttható, és
legyen
M
az a hipergráf a
V
(
H
)
-n, melynek élei az összes
p
,
…
,
(
p
+
k
−
1
)
-esek. Hasonlítsuk össze
H
-t
M
-mel a 13.20-beli szimmetrikus láncok
mindegyikében.
- 25. feladat F M
(a) Rögzítsünk egy
E
élt. Mit jelent az, ha
E
semelyik pontja sem fordul elő minden
élben? (b) Keressünk
j
olyan élt, melyek metszetében
legfeljebb
r
−
(
j
−
1
)
(
τ
(
H
)
−
1
)
pont van,
j
=
1
,
2
,
…
,
k
.
- 26. feladat F M
Vegyünk két élt, melyeknek egy közös pontja van,
és egy harmadikat, ha lehetséges, mely nem tartalmazza
ezt a pontot.
- 27. feladat F M
Vegyünk egy minimális olyan
W
-t, hogy a
H
W
bármelyik két éle metszi egymást. A
W
minden rendezésére, számoljuk le
azokat az
x
∈
W
pontokat, melyek első és utolsó
pontjai
H
W
-beli éleknek.
- 28. feladat F M
(a) Tetszőleges adott pontból legfeljebb egy
A
i
indul. (b) Számoljuk le kétféleképpen
az olyan éleket, melyek a
V
(
H
)
ciklikus permutációiban egymás utáni
pontokból állnak (vö. a Sperner tétel, 13.21a, második
megoldásával).
- 29. feladat F M
(a) Válasszunk egy olyan
S
halmazt, hogy
|
S
∩
E
|
≥
2
minden
E
élre, és
|
S
|
korlátos. (b) Ha
H
nem
ν
-kritikus, végezzünk indukciót
ν
-re.
- 30. feladat F M
Válasszuk az
x
1
,
…
,
x
t
pontokat úgy, hogy
x
i
+
1
egy maximális,
δ
i
+
1
fokú pont a
H
−
x
1
−
…
−
x
i
-ben. Mutassuk meg, hogy
|
E
(
H
−
x
1
−
…
−
x
i
)
|
≤
τ
∗
δ
i
+
1
.
- 31. feladat F M
(a) Írjuk fel az
egyenlőséget, és hasonlóan
v
r
,
u
r
−
1
,
v
r
−
1
-et is, és hasonlítsuk össze a
megfelelő tagokat
u
r
−
v
r
−
w
r
−
1
-ben és
u
r
−
1
−
v
r
−
1
−
w
r
−
2
-ben. (b) Tekintsünk egy minimális
fokú
x
pontot, és tekintsük a
H
−
x
,
H
−
E
(
H
−
x
)
hipergráfokat. Végezzünk indukciót
r
-re és
|
E
(
H
)
|
-re az (a) alapján. (c) Tegyük fel,
hogy a
H
bármely két éle metszi egymást, ahol
H
r
-uniform. Hány
r
-est tartalmazhatnak a
V
(
H
)
−
E
,
E
∈
E
(
H
)
halmazok?
- 32. feladat F M
(a) Használjunk a 13.21 és 13.27 megoldásához
hasonló érvelést; a pontok egy adott permutációjára
legfeljebb egy olyan
i
index van, hogy az
A
i
minden elemének kisebb az indexe, mint
a
B
i
minden elemének. (b) Ez az (a)
speciális esete.
- 33. feladat F M
Színezzük a pontokat egyenként; mikor
kényszerülnénk arra, hogy egy élt monokromatikussá
tegyünk?
- 34. feladat F M
Mutassuk meg először, hogy ha egy elsőfokú pont
van, és a többi másodfokú, akkor
H
2-kromatikus.
- 35. feladat F M
Tegyük fel, hogy
H
-nak nincs 1-elemű éle, és nincs
izolált pontja. Mutassuk meg, hogy (a) minden pont foka
legalább 2, (b) egy legalább negyedfokú pont csak
2-elemű élekhez tartozhat, (c) bármely két pont
hozzátartozik egy élhez.
- 36. feladat F M
Feltéve, hogy van egy 2-színezés, számoljuk le az
éleket két különböző módon; a monokromatikus párok
szerint, melyeket tartalmaznak, és a bikromatikus párok
szerint.
- 37. feladat F M
A „ha” rész megmutatásához keressünk egy
W
⊆
V
(
H
)
halmazt, hogy vagy a
|
W
∩
E
1
|
,
…
,
|
W
∩
E
m
|
halmazok mindegyike páros, vagy
közülük egy páratlan.
- 38. feladat F M
(a) Mutassuk meg, hogy egy
E
élt a diszjunkt
E
1
,
…
,
E
k
⊂
E
részhalmazokkal helyettesítve, nem
változtatjuk meg a feltevést. (b) Használjuk a
totálisan unimoduláris incidencia mátrixú hipergráfok
korábbi karakterizációját.
- 39. feladat F M
Egy páratlan kör incidencia mátrixa nem
unimoduláris.
- 40. feladat F M
Mutassuk meg, hogy egy minimális ellenpélda
tartalmazna egy összefüggő, feszítő 2-uniform
(hiper)gráfot.
- 41. feladat F M
Mutassuk meg, hogy a pontokat véletlenül
kiszínezve, annak a valószínűsége, hogy egy
monokromatikus élet kapunk, kisebb, mint 1 [vö.
13.12a].
- 42. feladat F M
Legyen
|
S
|
=
2
r
2
és legyenek az
S
halmaz
r
elemű részhalmazai egy másik
H
hipergráf pontjai; az
S
minden
P
=
{
X
,
Y
}
partíciójára azok az
r
-esek, melyek
X
-ben vagy
Y
-ban vannak, alkossák a
H
egy
E
p
élét. Mekkora lesz
τ
(
H
)
és
τ
∗
(
H
)
?
- 43. feladat F M
Tekintsünk újra egy véletlen színezést, de most
2.18-cal becsüljünk.
- 44. feladat F M
(a) Tekintsünk egy maximális fokú pontot. (b)
Hagyjuk el a legnagyobb fokú pontot mindegyik élből.
(c) Számoljuk le az éleket, melyek egy magasfokú
ponthoz illeszkednek.
- 45. feladat F M
(a) Válasszuk ki egy 2-elemű részhalmazát minden
élnek úgy, hogy ezek a részhalmazok egy erdőt
alkossanak. (b)
r
=
2
-re, a háromszög egy ilyen hipergráf.
Végezzünk indukciót
r
-re. (c) Tegyük fel, hogy van egy
nem-nulla vektor, mely ortogonális minden él
incidencia-vektorára, és tekintsük a negatív és pozitív
elemeit.
- 46. feladat F M
(a)-ra, használjuk a 13.45-beli konstrukció egy
módosítását; (b)-re, próbáljunk összeszorozni két
kisebb konstrukciót; (c)-re, keressünk egy egyszerű
direkt példát.
- 47. feladat F M
Válasszunk egy
k
-elemű
X
halmazt minden
1
≤
k
≤
r
-re úgy, hogy az
X
-et tartalmazó élek száma több, mint
|
E
(
H
)
|
∕
r
k
.
- 48. feladat F M
Legyen
V
(
H
)
=
{
v
1
,
…
,
v
n
}
,
E
(
H
)
=
{
E
1
,
…
,
E
m
}
,
és
A
=
(
a
i
j
)
i
=
1
,
n
j
=
1
m
. Ekkor
ν
∗
(
H
)
értéke az
1
T
x
maximuma, azon feltételek mellett,
hogy
A
x
≤
1
és
x
≥
0
.
- 49. feladat F M
(a) Bontsuk szét direkt módon, de vegyük
figyelembe a pontok multiplicitását. (b) Használjuk
7.40-et. (c) Vannak optimális törtfedések (párosítások)
racionális súlyokkal. Csökkentsük a súlyok legkisebb
közös nevezőjét, felhasználva (a)-t és (b)-t. (d)
2
ν
∗
(
G
)
a 2-párosítások maximális mérete.
2
τ
∗
(
G
)
az a formula, mely 7.37-ben van
megadva
ν
2
(
G
)
-re.
- 50. feladat F M
Használjunk olyan konstrukciót, mely az előző
megoldásbelihez hasonlít.
- 51. feladat F M
(a) A második egyenlőtlenség bizonyításához
vegyük észre, hogy ha
S
⊆
V
(
G
⊗
H
)
lefedi a
G
⊗
H
összes élét, akkor
S
∩
(
V
(
G
)
⊗
F
)
-nek legalább
τ
(
G
)
eleme van a
H
minden
F
élére. (b) Az „akkor” rész könnyű (a)
szerint; a „csak akkor” bizonyításához, tegyük fel,
hogy
τ
n
(
H
)
<
n
τ
(
H
)
, és
G
álljon egy
N
elemű halmaz összes
(
N
−
n
)
-elemű részhalmazából (
N
nagy). (c) Használjuk 13.30-at
τ
(
H
p
)
becslésére.
- 52. feladat F M
Ha egy
x
pont a különböző
E
1
,
E
2
élekhez illeszkedik, vegyük a
H
−
{
E
1
}
és
H
−
{
E
2
}
hipergráfok egy-egy
(
τ
−
1
)
-elemű fedésének „átlagát”.
- 53. feladat F M
Vegyük a
H
−
v
,
v
∈
E
0
∈
E
(
H
)
maximális párosításainak az
„átlagát”.
- 54. feladat F M
Meg kell mutatnunk, hogy egy
τ
-kritikus kiegyensúlyozott hipergráf
diszjunkt élekből áll. Másoljuk le a 7.2 második
megoldását.
- 55. feladat F M
Az (i)
⇒
(iii) bizonyításához, vegyük észre,
hogy egy minimális ellenpélda
ν
-kritikus lenne.
- 56. feladat F M
Mutassuk meg, és használjuk a következő tényt: Ha
egy
H
hipergráf kielégíti (iv)-t, akkor
minden olyan
H
0
hipergráf, mely az élek
megsokszorozásával keletkezik, szintén kielégíti
(iv)-t. (A megsokszorozásba beleértjük a 0-val való
szorzást, azaz az elhagyást is.)
- 57. feladat F M
Tegyük fel, hogy
G
perfekt; rendeljük a
H
hipergráfhoz azt a
G
gráfot, melyre
L
(
H
)
≅
G
.