Details

Autor(en) / Beteiligte

• Lefmann, Hanno
• Rödl, Vojtech
• Wysocka, Beata

Titel

Multicolored Subsets in Colored Hypergraphs

Ist Teil von

• Journal of combinatorial theory. Series A, 1996-05, Vol.74 (2), p.209-248

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

1996

Quelle

Elsevier Journal Backfiles on ScienceDirect (DFG Nationallizenzen)

Beschreibungen/Notizen

• We consider anti-Ramsey type problems fork-uniform hypergraphs. A subsetYof ann-element setXis totally multicolored, if the restriction of a coloring ofk-element subsets ofXto [Y]kis a one-to-one coloring. We study the maximum size of totally multicolored subsets for colorings which satisfy the following restriction: any two distinctk-element subsets with at least h elements in the intersection are colored differently. It is shown that the size of the largest totally multicolored subset can be bounded from below by[formula]whereckis a positive constant and this lower bound is sharp (up to a multiplicative constant). Extending earlier results of present and other authors, various related problems concerning edge-colorings of complete graphs are considered. We consider also some application to Sidon sets in arbitrary groups. We show for example the existence of a proper coloring of [X]2with no totally multicolored subset of size 2.21n1/3(lnn)1/3, providedn⩾n0. This sharpens an earlier result of L. Babai and is up to a multiplicative constant the best possible (this follows e.g. from the above mentioned result applied withk=2 andh=1). As a tool for proving the existence of such a coloring we derive an upper bound for permanents of rectangular (0, 1)-matrices