×

Colorful flowers. (English) Zbl 1177.05080

Summary: For a set \(A\) let \([A]^k\) denote the family of all \(k\)-element subsets of \(A\). A function \(f:[A]^k\rightarrow C\) is a local coloring if it maps disjoint sets of \(A\) into different elements of \(C\). A family \(\mathcal F\subseteq [A]^k\) is called a flower if there exists \(E\in [A]^{k - 1}\) so that \(|F\cap F{^{\prime}}|=E\) for all \(F,F^\prime \in \mathcal F, F\neq F{^{\prime}}\). A flower is said to be colorful if \(f(F)\neq f(F{^{\prime}})\) for any two \(F,F^\prime \in \mathcal F\). In the paper we find the smallest cardinal \(\gamma \) such that there exists a local coloring of \([A]^k\) containing no colorful flower of size \(\gamma \). As a consequence we answer a question raised by J. Pelant, P. Holický, and O.F.K. Kalenda [Fundam. Math. 192, No.3, 245–254 (2006; Zbl 1118.46028)]. We also discuss a few results and conjectures concerning a generalization of this problem.

MSC:

05C65 Hypergraphs
05D10 Ramsey theory
05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs (2000), Wiley: Wiley New York
[2] Katona, G. O.H., Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar., 15, 329-337 (1964) · Zbl 0134.25101
[3] Lovász, L., Kneser’s conjecture, chromatic numbers and homotopy, J. Combin. Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028
[4] Pelant, J.; Holický, P.; Kalenda, O. F.K., \(C(K)\) spaces which cannot be uniformly embedded into \(c_0(\Gamma)\), Fund. Math., 192, 245-254 (2006) · Zbl 1118.46028
[5] Pelant, J.; Rödl, V., On coverings of infinite-dimensional metric spaces, Discrete Math., 108, 75-81 (1992) · Zbl 0773.54017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.