Halmazrendszerek speciálkollégium, Hajnal Péter X. 7. (1 óra)

Definíció: ν_{k} definíciója.

ν_{k} tulajdonságai:

(i) ν^{∗}(H) ≥ \frac{ν_{k}(H)}{k} ≥ ν(H), (ii) ν_{k+l}(H ≥ ν_{k}(H) + ν_{l}(H), (iii) alkalmas k-ra ν^{∗}(H) = \frac{ν_{k}(H)}{k}, (iv) lim_{k→∞} \frac{ν_{k}(H)}{k} = ν^{∗}(H).

τ_{k}(H)-ról hasonló tulajdonságok igazolhatók.

ν_{k} és τ_{k} mennyiségek gráfok esetén

Lemma: ν_{2}(G) = τ_{2}(G). Következmény: τ^{∗}(G) = \frac{τ_{2}(G)}{2} = \frac{ν^{∗}(G)}{2} = ν^{∗}(G). Következmény: G r-reguláris gráf esetén ν_{2}(G) = |V (G)|. Lemma: τ_{2}(G) ≤ ν(G) + τ(G). Következmény: ν(G) > \frac{ν_{2}(G)}{2} = ν^{∗}(G) = τ^{∗}(G) = \frac{τ_{2}(G)}{2} = τ(G) nem lehetséges. Lemma: τ_{k}(H) = τ_{2}(H) + τ_{k−2}(H).

Kőnig-tulajdonság

Definíció: H Kőnig-tulajdonságú, ha ν(H) = τ(H). Példa: Páros gráfok. Példa: Intervallum halmazrendszerek. Példa: Egy általános helyzetű véges ponthalmaz összes nyilt háromszöge. Definíció: Totálisan unimoduláris mátrix. Totálisan unimoduláris halmazrendszer. Példa: (totálisan unimoduláris halmazrendszerre) Páros gráf Példa: (Kőnig-tulajdonságra) Totálisan unimoduláris halmazrendszerek. Lemma: Ha egy Ax ≤ b lineáris programozási feladat A mátrixa totálisan unimoduláris és b egész, akkor lesz egész értékű optimális megoldás is. Következmény: Ha H totálisan unimoduláris halmazrendszer, akkor τ^{∗}(H) = τ(H) és ν^{∗}(H) = ν(H). Speciálisan H Kőnig-tulajdonságú.

Feladat lehet: kombinatorikusan jellemezzük a totálisan unimoduláris halmazrendszereket.