Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs. Issue 1 (6th August 2012) - Lefmann, Hanno
Abstract For k‐uniform hypergraphs F and H and an integer r≥2, let cr, F(H) denote the number of r‐colorings of the set of hyperedges of H with no monochromatic copy of F and let cr, F(n)=maxH∈Hncr, F(H), where the maximum is taken over the family Hn of all k‐uniform hypergraphs on n vertices. Moreover, let ex (n, F) be the usual extremal function, i.e., the maximum number of hyperedges of an n‐vertex k‐uniform hypergraph which contains no copy of F. Here, we consider the question for determining cr, F(n) for F being the k‐uniform expanded, complete graph Hℓ+1k or the k‐uniform Fan(k)‐hypergraph Fℓ+1k with core of size (ℓ+1), where ℓ≥k≥3, and we show cr, F(n)=r ex (n, F) for r=2, 3 and n large enough. Moreover, for r=2 or r=3, for k‐uniform hypergraphs H on n vertices, the equality cr, F(H)=r ex (n, F) only holds if H is isomorphic to the ℓ‐partite, k‐uniform Turán hypergraph on n vertices, once n is large enough. On the other hand, we show that cr, F(n) is exponentially larger than r ex (n, F), if r≥4.