Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs. Issue 1 (6th August 2012) - Lefmann, Hanno; Person, Yury
Abstract For k‐uniform hypergraphs F and H and an integer <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px85f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r≥2, let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px87j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr, F(H) denote the number of r‐colorings of the set of hyperedges of H with no monochromatic copy of F and let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px860" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr, F(n)=maxH∈Hncr, F(H), where the maximum is taken over the family <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px82s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Hn of all k‐uniform hypergraphs on n vertices. Moreover, let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px817" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> 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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px84w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr, F(n) for F being the k‐uniform expanded, complete graph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px83b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Hℓ+1k or the k‐uniform Fan(k)‐hypergraph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px80p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Fℓ+1k with core of size <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7zm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(ℓ+1), where <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px78k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℓ≥k≥3, and we show <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7fb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr, F(n)=r ex (n, F) for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7ds" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r=2, 3 and n large enough. Moreover, for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7c7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r=2 or <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7bp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r=3, for k‐uniform hypergraphs H on n vertices, the equality <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7kj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7j0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr, F(n) is exponentially larger than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7hf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r ex (n, F), if <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7gw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r≥4.