Graf, twierdzenie Halla

[matinf]

Hej,

Mam takie zadanie, do którego jest wskazówka, ale nadal nie wiem jak.

Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.

Wskazówka jest taka:
Dołożyć \(\displaystyle{ n - k}\) chłopaków, ale tak że każda dziewczyna zna ich wszystkich (nowa sytuacja)


Pokazać, że co najmniej k dziewcząt w starej sytuacji możne znaleźć wszystkich mężów wtw gdy
wszystkie mogą w nowej sytuacji.


No więc ten lemat mogę pokazać:

=>)

To jasne, każda z dziewczyna, która nie znalazła jeszcze męża, na pewno go znajdzie,
bo w nowej sytuacji będzie \(\displaystyle{ n - k}\) chłopaków (każda dziewczyna ich zna)


<=)

To też jasne chyba. Wszystkie dziewczyny znalazły mężów, w nowej sytuacji.
Jeśli "zużyły" wszystkich \(\displaystyle{ n - k}\) "nowych" to wówczas \(\displaystyle{ k}\) musiało być starych
(jeśli zużyły trochę mniej, to więcej "starych" -stąd co najmniej)
Więc jasne, że conajmniej \(\displaystyle{ k}\) dziewcząt można ożenić w starej sytuacji.


Dalej jest wskazówka, żeby zastosować twierdzenie Halla w nowej sytuacji.

Czyli, że można pożenić wtw gdy każdy podzbiór dziewczyn, "razem zna"
nie mniejszy podzbiór chłopaków,

Ale nie wiem jak to dokończyć.

Jakieś wskazówki ?

[norwimaj]

Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.

Czy tam nie miało być \(\displaystyle{ k-n+r}\) zamiast \(\displaystyle{ n-k+r}\)? Dla \(\displaystyle{ k=0}\) warunek po prawej stronie powinien być zawsze prawdziwy.

[matinf]

Pokazać, że w dowolnej grupie złożonej z \(\displaystyle{ n}\) dziewcząt i \(\displaystyle{ m}\) chłopców
istniej \(\displaystyle{ k}\) dziewcząt, którym można znaleźć mężów wtw gdy dowolny podzbiór
spośród \(\displaystyle{ n}\) dziewcząt (powiedzmy \(\displaystyle{ r}\) spośród nich) zna co najmniej \(\displaystyle{ n - k + r}\) chłopców.

Czy tam nie miało być \(\displaystyle{ k-n+r}\) zamiast \(\displaystyle{ n-k+r}\)? Dla \(\displaystyle{ k=0}\) warunek po prawej stronie powinien być zawsze prawdziwy.

Tak, masz rację.

[norwimaj]

To teraz już łatwo możesz udowodnić ostatnią brakującą równoważność: zachodzi warunek Halla w nowej sytuacji wtw dowolny \(\displaystyle{ r}\)-podzbiór dziewcząt zna co najmniej \(\displaystyle{ k - n + r}\) starych (tzn. nie tych dołożonych) chłopców.

[matinf]

czyli lemat dobrze pokazałem ?

Ja rozumiem logikę tego dowodu. Na prawdę pokazanie równoważności, o której mówisz da tezę.

Ale tej równoważności nie widzę jak pokazać. Mimo, że jak twierdzisz to łatwe, to wcale nie jest łatwe.

[norwimaj]

W jedną stronę mogę spróbować. Załóżmy, że jest spełniony warunek Halla w nowej sytuacji. Chcemy pokazać, że dowolny zbiór \(\displaystyle{ r}\) dziewcząt zna co najmniej \(\displaystyle{ k-n+r}\) chłopaków w starej sytuacji. Dla \(\displaystyle{ r=0}\) (złośliwy przypadek, łatwy do przeoczenia) liczba \(\displaystyle{ k-n+r}\) jest niedodatnia, więc tezę mamy za darmo. Jeśli \(\displaystyle{ r>0}\), to wybrane dziewczęta znają co najmniej \(\displaystyle{ r}\) chłopaków, w tym \(\displaystyle{ n-k}\) nowych. Znają więc co najmniej \(\displaystyle{ r-(n-k)}\) starych.