Kneser graphs are like Swiss cheese

Kneser graphs are like Swiss cheese, Discrete Analysis 2018:2, 18 pp. This paper relates two very interesting areas of research in extremal combinatorics: removal lemmas, and influence of variables. A _removal lemma_ is a result that states that if $S$ is a set that contains only few copies of a certain structure, then one can remove just a few elements from $S$ to create a set $S'$ that has no copies of that structure. For instance, the triangle removal lemma states that a graph with few triangles can be approximated by a graph with no triangles. Removal lemmas play a very important role in extremal and additive combinatorics. As for the influence of variables, the aspect that is of interest here is that there are many interesting theorems that state that if a function has a certain property, it must be because in a certain sense it depends on only a few variables. For example, a famous result of the first author shows that if a monotone graph property fails to have a sharp threshold, then the property can be approximated by one for which the minimal graphs that satisfy it are all small, with the result that the "influence" of individual edges on whether the graph has the property is substantial. The main result of this paper is an "edge removal lemma" for various families of graphs. It states that if $G$ is a graph in one of these families, then for every set $X$ of vertices in $G$ that spans only a few edges one can throw away just a small proportion of $X$ to obtain a subset $X'$ that is independent. Of course, a result like this is completely false in general: one has only to take a sparse random graph, and then every subset will span few edges but no large subset will be independent. But it is true, for example, for complete bipartite graphs, since a set of vertices that spans a sparse subgraph will have to be contained almost entirely in one of the two vertex sets, and then one can throw away the vertices that are in the other set. One of the families for which the authors prove an edge-removal lemma is that of Kneser graphs. For $0

Keywords:

• Independent set
• Combinatorics
• Swiss cheese
• Kneser graph
• Graph
• Mathematics
• Bipartite graph
• Random graph
• Graph property
• Vertex (geometry)
• Disjoint sets
• Complete graph

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader