A structural result for hypergraphs with many restricted edge colorings

For $k$-uniform hypergraphs $\cF$ and $\cH$ and an integer $r\geq2$,let $c_{r,\cF}(\cH)$ denote the number of$r$-colorings of the set of hyperedges of $\cH$ with no monochromaticcopy of $\cF$ andlet $c_{r,\cF}(n)=\max_{\cH\in\ccHn} c_{r,\cF}(\cH)$,where the maximum runs over the family $\mathcal{H}_n$ of all$k$-uniform hypergraphs on $n$ vertices. Moreover, let $\ex(n,\cF)$ bethe usual \emph{Turán function}, i.e., the maximumnumber of hyperedges of an $n$-vertex $k$-uniform hypergraph whichcontains no copy of~$\cF$.

In this paper, we consider the question for determining $c_{r,F}(n)$for arbitrary fixed hypergraphs $\cF$ and show%\[c_{r,\cF}(n)=r^{\ex(n,\cF)+o(n^k)}\]%for $r=2,3$. Moreover, we obtain a structural result for $r=2,3$ and any$\cH$ with $c_{r,\cF}(\cH)\ge r^{\ex(|V(\cH)|,\cF)}$ under the assumptionthat a stability result for the $k$-uniform hypergraph $\cF$ exists and$|V(H)|$ is sufficiently large. We also obtain exact resultsfor $c_{r,\cF}(n)$ when $\cF$ is a $3$- or $4$-uniform generalized triangleand $r=2,3$, while $c_{r,\cF}(n)\gg r^{\ex(n,\cF)}$ for $r\ge4$and $n$ sufficiently large.

Full Text (PDF format)

Published 1 January 2010