Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal. Issue 3 (9th May 2014) - Linial, Nati; Morgenstern, Avraham
Abstract For given integers <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdhz7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k, l</alternatives> we ask whether every large graph with a sufficiently small number of k‐cliques and k‐anticliques must contain an induced copy of every l‐vertex graph. Here we prove this claim for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdj75" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k=l=3</alternatives> with a sharp bound. A similar phenomenon is established as well for tournaments with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzdj6m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k=l=4</alternatives>.