|
Algebra and Discrete Mathematics, 2005, Issue 1, Pages 84–91
(Mi adm291)
|
|
|
|
RESEARCH ARTICLE
Color-detectors of hypergraphs
I. V. Protasov, O. I. Protasova Department of Cybernetics, Kyiv University, Volodimirska 64, Kyiv GSP, Ukraine
Abstract:
Let X be a set of cardinality k, F be a family of subsets of X. We say that a cardinal λ,λ<k, is a color-detector of the hypergraph H=(X,F) if card χ(X)≤λ for every coloring χ:X→k such that card χ(F)≤λ for every F∈F. We show that the color-detectors of H are tightly connected with the covering number cov(H)=cup{α:any αpoints of X are contained in some F∈F}. In some cases we determine all of the color-detectors of H and their asymptotic counterparts. We put also some open questions.
Keywords:
hypergraph, color-detector, covering number.
Received: 18.10.2004 Revised: 24.03.2005
Citation:
I. V. Protasov, O. I. Protasova, “Color-detectors of hypergraphs”, Algebra Discrete Math., 2005, no. 1, 84–91
Linking options:
https://www.mathnet.ru/eng/adm291 https://www.mathnet.ru/eng/adm/y2005/i1/p84
|
Statistics & downloads: |
Abstract page: | 139 | Full-text PDF : | 67 | References: | 5 | First page: | 1 |
|