Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs. Issue 1 (6th August 2012)

• Record Type: Journal Article
• Authors: Lefmann, Hanno; Person, Yury
• Is Part Of: Journal of graph theory. Volume 73:Issue 1(2013)
• Page Start: 1
• Page End: 31
• Publication Date: 2012-08-06
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21653
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>For <italic>k</italic>‐uniform hypergraphs <italic>F</italic> and <italic>H</italic> and an integer <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px85f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math>, let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px87j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> denote the number of <italic>r</italic>‐colorings of the set of hyperedges of <italic>H</italic> with no monochromatic copy of <italic>F</italic> and let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px860" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msub><mml:mo movablelimits="true" form="prefix">max</mml:mo><mml:mrow><mml:mi>H</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi mathvariant="script">H</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:msub><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math>, 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi mathvariant="script">H</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:math> of all <italic>k</italic>‐uniform hypergraphs on <italic>n</italic> vertices. Moreover, let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px817" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi> ex </mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> be the usual extremal function, i.e., the maximum number of hyperedges of an <italic>n</italic>‐vertex <italic>k</italic>‐uniform hypergraph which contains no copy of <italic>F</italic>. 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> for <italic>F</italic> being the <italic>k</italic>‐uniform expanded, complete graph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px83b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>H</mml:mi><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>k</mml:mi></mml:msubsup></mml:math> or the <italic>k</italic>‐uniform Fan(<italic>k</italic>)‐hypergraph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px80p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>F</mml:mi><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>k</mml:mi></mml:msubsup></mml:math> with core of size <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7zm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>, where <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px78k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>≥</mml:mo><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math>, and we show <disp-formula content-type="mathematics" id="jgt21653-disp-0001"><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7fb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mi>r</mml:mi><mml:mrow><mml:mi> ex </mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:math></disp-formula>for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7ds" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math> and <italic>n</italic> large enough. Moreover, for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7c7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> or <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7bp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math>, for <italic>k</italic>‐uniform hypergraphs <italic>H</italic> on <italic>n</italic> vertices, the equality <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7kj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0015" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mi>r</mml:mi><mml:mrow><mml:mi> ex </mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:math> only holds if <italic>H</italic> is isomorphic to the ℓ‐partite, <italic>k</italic>‐uniform Turán hypergraph on <italic>n</italic> vertices, once <italic>n</italic> 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0016" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mrow><mml:mi>r</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi></mml:mrow></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> is exponentially larger than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7hf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0017" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>r</mml:mi><mml:mrow><mml:mi> ex </mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>F</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup></mml:math>, if <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1v9px7gw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21653:equation:jgt21653-math-0018" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math>.</p> </abstract>