Partition-crossing hypergraphs
For a finite set X, we say that a set H ⊆ X crosses a partition P = (X1, . . . , Xk) of X if H intersects min(|H|, k) partition classes. If |H| ≥ k, this means that H meets all classes Xi, whilst for |H| ≤ k the elements of the crossing set H belong to mutually distinct classes. A set system H cross...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2018
|
| Sorozat: | Acta cybernetica
23 No. 3 |
| Kulcsszavak: | Hipergráf, Gráfelmélet |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/55679 |
| LEADER | 01971nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta55679 | ||
| 005 | 20220620155503.0 | ||
| 008 | 181108s2018 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Bujtás Csilla | |
| 245 | 1 | 0 | |a Partition-crossing hypergraphs |h [elektronikus dokumentum] / |c Bujtás Csilla |
| 260 | |c 2018 | ||
| 300 | |a 815-828 | ||
| 490 | 0 | |a Acta cybernetica |v 23 No. 3 | |
| 520 | 3 | |a For a finite set X, we say that a set H ⊆ X crosses a partition P = (X1, . . . , Xk) of X if H intersects min(|H|, k) partition classes. If |H| ≥ k, this means that H meets all classes Xi, whilst for |H| ≤ k the elements of the crossing set H belong to mutually distinct classes. A set system H crosses P, if so does some H ∈ H. The minimum number of r-element subsets, such that every k-partition of an n-element set X is crossed by at least one of them, is denoted by f(n, k, r). The problem of determining these minimum values for k = r was raised and studied by several authors, first by Sterboul in 1973 [Proc. Colloq. Math. Soc. J. Bolyai, Vol. 10, Keszthely 1973, North-Holland/American Elsevier, 1975, pp. 1387–1404]. The present authors determined asymptotically tight estimates on f(n, k, k) for every fixed k as n → ∞ [Graphs Combin., 25 (2009), 807–816]. Here we consider the more general problem for two parameters k and r, and establish lower and upper bounds for f(n, k, r). For various combinations of the three values n, k, r we obtain asymptotically tight estimates, and also point out close connections of the function f(n, k, r) to Tur´an-type extremal problems on graphs and hypergraphs, or to balanced incomplete block designs. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Matematika | |
| 695 | |a Hipergráf, Gráfelmélet | ||
| 700 | 0 | 1 | |a Tuza Zsolt |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/55679/1/actacyb_23_3_2018_06.pdf |z Dokumentum-elérés |