Bujtás Csilla; Tuza Zsolt: Partition-crossing hypergraphs. In: Acta cybernetica, (23) 3. pp. 815-828. (2018)
Előnézet |
Cikk, tanulmány, mű
actacyb_23_3_2018_06.pdf Letöltés (414kB) | Előnézet |
Absztrakt (kivonat)
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.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2018 |
| Kötet: | 23 |
| Szám: | 3 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 815-828 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/55467/ |
| Kulcsszavak: | Hipergráf, Gráfelmélet |
| Megjegyzések: | Bibliogr.: p. 827-828. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika |
| Feltöltés dátuma: | 2018. nov. 08. 08:21 |
| Utolsó módosítás: | 2022. jún. 20. 15:55 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/55679 |
 |
Tétel nézet |
