Partition-crossing hypergraphs

DOI10.14232/ACTACYB.23.3.2018.6MaRDI QIDQ4584655zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Csilla Bujtás, Zsolt Tuza

Publication date 3 September 2018

Published in Acta Cybernetica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09622

zbMATH Keywords

crossing sethypergraphpartitionset systemTurán-type problemupper chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a finite set $X$, we say that a set $HsubseteqX$ crosses a partition $calP=(X_1,dots,X_k)$ of $X$ if $H$ intersects $min(|H|,k)$ partition classes. If $|H|geqk$, this means that $H$ meets all classes $X_i$, whilst for $|H|leqk$ the elements of the crossing set $H$ belong to mutually distinct classes. A set system $calH$ crosses $calP$, if so does some $HincalH$. 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 $noinfty$ [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.

Recommendations

• Smallest set-transversals of \(k\)-partitions
• Cross-intersecting pairs of hypergraphs
• The Chromatic Number of Kneser Hypergraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• Independent Transversals in Sparse Partite Hypergraphs

Cited in

(3)

• Partial cubes and crossing graphs
• Cross-intersecting pairs of hypergraphs
• Smallest set-transversals of \(k\)-partitions

This page was built for publication: Partition-crossing hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584655)