Multicolored subsets in colored hypergraphs (Q1914009): Difference between revisions

Let \(X\) be an \(n\)-element set. Let \(\Delta : [K]^k \to \omega\), where \(\omega = \{0,1, \dots\}\), be a coloring of the \(k\)-element subsets of \(X\), where \(|Z \cap Z^* |< h\) for any two distinct \(k\)-element subsets \(Z, Z^* \in [X]^k\) with \(\Delta (Z) = \Delta (Z^*)\). A subset \(Y \subseteq X\) is called totally multicolored if the restriction of \(\Delta\) to \([Y]^k\) is a one-to-one coloring. Define \(f(n,k,h) = \max \{|Y |: Y \subseteq X\) is totally multicolored\}. \textit{L. Babai} [Graphs Comb. 1, 23-28 (1985; Zbl 0581.05040)] gave bounds for \(f(n,2,1)\), and \textit{N. Alon}, \textit{H. Lefmann} and \textit{V. Rödl} [Colloq. Math. Soc. János Bolyai 60, 9-22 (1991; Zbl 0791.05075)] obtained bounds for \(f(n,k,1)\). In the present paper, using probabilistic methods, the authors give the following extension: Let \(h,k\) be positive integers with \(h < k\) and \(2 \leq k\). Then there exist positive constants \(c_k\), \(c^*_k\) such that for every integer \(n\), with \(n\) large, \[ c_k \cdot (\ln n)^{1/(2k - 1)} \cdot n^{(k - h) (2k - 1)} \leq f(n,k,h) \leq c^*_k \cdot (\ln n)^{1/(2k - 1)} \cdot n^{(k - h) (2k - 1)}. \] For \(f(n,2,1)\), they get the more explicit upper bound \(2.2 \cdot (n \cdot \ln n)^{1/3}\).