Bujtás, Csilla and Tuza, Zsolt: Partitioncrossing hypergraphs. In: Acta cybernetica, (23) 3. pp. 815828. (2018)

Cikk, tanulmány, mű
actacyb_23_3_2018_06.pdf Download (414kB)  Preview 
Abstract
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 relement subsets, such that every kpartition of an nelement 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, NorthHolland/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´antype extremal problems on graphs and hypergraphs, or to balanced incomplete block designs.
Item Type:  Article 

Journal or Publication Title:  Acta cybernetica 
Date:  2018 
Volume:  23 
Number:  3 
ISSN:  0324721X 
Page Range:  pp. 815828 
Uncontrolled Keywords:  Hipergráf, Gráfelmélet 
Additional Information:  Bibliogr.: p. 827828. ; Összefoglalás angol nyelven 
Date Deposited:  2018. Nov. 08. 08:21 
Last Modified:  2018. Nov. 08. 08:21 
URI:  http://acta.bibl.uszeged.hu/id/eprint/55679 
Actions (login required)
View Item 