Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal. Issue 3 (9th May 2014)

• Record Type: Journal Article
• Authors: Linial, Nati; Morgenstern, Avraham
• Is Part Of: Journal of graph theory. Volume 78:Issue 3(2015)
• Page Start: 229
• Page End: 238
• Publication Date: 2014-05-09
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21801
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>For given integers <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdhz7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21801:jgt21801-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>, </mml:mo><mml:mi>l</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> we ask whether every large graph with a sufficiently <italic>small</italic> number of <italic>k</italic>‐cliques and <italic>k</italic>‐anticliques must contain an induced copy of every <italic>l</italic>‐vertex graph. Here we prove this claim for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdj75" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21801:jgt21801-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mi>l</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> with a sharp bound. A similar phenomenon is established as well for tournaments with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdj6m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21801:jgt21801-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mi>l</mml:mi><mml:mo>=</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>.</p> </abstract>