The tensor power of the clique on @math vertices (denoted by @math ) is the graph on vertex set @math such that two vertices @math are connected if and only if @math for all @math . Let the density of a subset @math of @math to be @math , and let the vertex boundary of a set @math to be vertices which are incident to some vertex of @math , perhaps including points of @math . We investigate two similar problems on such graphs. First, we study the vertex isoperimetry problem. Given a density @math what is the smallest possible density of the vertex boundary of a subset of @math of density @math ? Let @math be the infimum of these minimum densities as @math . We find a recursive relation allows one to compute @math in time polynomial to the number of desired bits of precision. Second, we study given an independent set @math of density @math , how close it is to a maximum-sized independent set @math of density @math . We show that this deviation (measured by @math ) is at most @math as long as @math . This substantially improves on results of Alon, Dinur, Friedgut, and Sudakov (2004) and Ghandehari and Hatami (2008) which had an @math upper bound. We also show the exponent @math is optimal assuming @math tending to infinity and @math tending to @math . The methods have similarity to recent work by Ellis, Keller, and Lifshitz (2016) in the context of Kneser graphs and other settings. The author hopes that these results have potential applications in hardness of approximation, particularly in approximate graph coloring and independent set problems.
A result which also finds a tight'' super constant exponent @math for the independent set stability is proved in some very recent work @cite_24 @cite_10 @cite_4 @cite_6 @cite_18 @cite_16 on Kneser graphs and related structures. (See also @cite_14 and Proposition 4.3 of @cite_8 .) The techniques have high-level similarity to the ones adopted here: The author became aware of these similar proofs only after writing major portions of the manuscript. particularly in their use of compressions to prove a isoperimetric inequality which they then bootstrap to a combinatorial independent set stability result.
@cite_18 @cite_14 @cite_4 @cite_8 @cite_6 @cite_24 @cite_16 @cite_10
2896300682 2606627981 2531394623 2529480917 2339165222 2336459687 2609098951 2757077271
A family @math of graphs on a fixed set of @math vertices is called triangle-intersecting if for any @math , the intersection @math contains a triangle. More generally, for a fixed graph @math , a family @math is @math -intersecting if the intersection of any two graphs in @math contains a sub-graph isomorphic to @math . In [D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), pp. 841--885], Ellis, Filmus and Friedgut proved a 36-year old conjecture of Simonovits and Sos stating that the maximal size of a triangle-intersecting family is @math . Furthermore, they proved a @math -biased generalization, stating that for any @math , we have @math , where @math is the probability that the random graph @math belongs to @math . In the same paper, conjectured that the assertion of their biased theorem holds also for @math , and more generally, that for any non- @math -colorable graph @math and any @math -intersecting family @math , we have @math for all @math . In this note we construct, for any fixed @math and any @math , an @math -intersecting family @math of graphs such that @math , where @math depends only on @math and @math , thus disproving both conjectures. A family of sets is said to be if its automorphism group is transitive, and if any two sets in the family have nonempty intersection. Our purpose here is to study the following question: for @math with @math , how large can a symmetric intersecting family of @math -element subsets of @math be? As a first step towards a complete answer, we prove that such a family has size at most [ (- c(n-2k) n k( n - k) ) n k , ] where @math is a universal constant. We also describe various combinatorial and algebraic approaches to constructing such families. A family of sets is said to be if any two sets in the family have nonempty intersection. In 1973, Erd o s raised the problem of determining the maximum possible size of a union of @math different intersecting families of @math -element subsets of an @math -element set, for each triple of integers @math . We make progress on this problem, proving that for any fixed integer @math and for any @math , if @math is an @math -element set, and @math , where each @math is an intersecting family of @math -element subsets of @math , then @math , with equality only if @math for some @math with @math . This is best possible up to the size of the @math term, and improves a 1987 result of Frankl and F "uredi, who obtained the same conclusion under the stronger hypothesis @math , in the case @math . Our proof utilises an isoperimetric, influence-based method recently developed by Keller and the authors. The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a @math -uniform @math -intersecting family on @math points, and describes all optimal families. We extend this theorem to several other settings: the weighted case, the case of infinitely many points, and the Hamming scheme. The weighted Ahlswede-Khachatrian theorem gives the maximal @math measure of a @math -intersecting family on @math points, where @math . As has been observed by Ahlswede and Khachatrian and by Dinur and Safra, this theorem can be derived from the classical one by a simple reduction. However, this reduction fails to identify the optimal families, and only works for @math , using a different technique of Ahlswede and Khachatrian (the case @math is Katona's intersection theorem). We then extend the weighted Ahlswede-Khachatrian theorem to the case of infinitely many points. The Ahlswede-Khachatrian theorem on the Hamming scheme gives the maximum cardinality of a subset of @math in which any two elements @math have @math positions @math such that @math . We show that this case corresponds to @math with @math , extending work of Ahlswede and Khachatrian, who considered the case @math . We also determine the maximum cardinality families. We obtain similar results for subsets of @math , though in this case we are not able to identify all maximum cardinality families. A set family F is said to be t-intersecting if any two sets in F share at least t elements. The Complete Intersection Theorem of Ahlswede and Khachatrian (1997) determines the maximal size f(n,k,t) of a t-intersecting family of k-element subsets of 1,2,...,n , and gives a full characterisation of the extremal families. In this paper, we prove the following stability version' of the theorem: if k n is bounded away from 0 and 1 2, and F is a t-intersecting family of k-element subsets of 1,2,...,n such that @math , then there exists an extremal family G such that @math . For fixed t, this assertion is tight up to a constant factor. This proves a conjecture of Friedgut from 2008. Our proof combines classical shifting arguments with a bootstrapping' method based upon an isoperimetric argument. Erdős-Ko-Rado (EKR) type theorems yield upper bounds on the sizes of families of sets, subject to various intersection requirements on the sets in the family. Stability versions of such theorems assert that if the size of a family is close to the maximum possible size, then the family itself must be close (in some appropriate sense) to a maximum-sized family. In this paper, we present an approach to obtaining stability versions of EKR-type theorems, via isoperimetric inequalities for subsets of the hypercube. Our approach is rather general, and allows the leveraging of a wide variety of exact EKR-type results into strong stability versions of these results, without going into the proofs of the original results. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on @math -intersecting families of @math -element subsets of @math (for @math ), and to show that, somewhat surprisingly, all these results hold when the intersection requirement is replaced by a much weaker requirement. Other examples include stability versions of Frankl's recent result on the Erdős matching conjecture, the Ellis-Filmus-Friedgut proof of the Simonovits-Sos conjecture, and various EKR-type results on @math -wise (cross)- @math -intersecting families. The full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary @math of a set @math , as a function of @math . A weaker (but more widely-used) lower bound is @math , where equality holds iff @math is a subcube. In 2011, the first author obtained a sharp stability' version of the latter result, proving that if @math , then there exists a subcube @math such that @math . The weak' version of the edge isoperimetric inequality has the following well-known generalization for the @math -biased' measure @math on the discrete cube: if @math , or if @math and @math is monotone increasing, then @math . In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if @math , then there exists a subcube @math such that @math , where @math . This result is a central component in recent work of the authors proving sharp stability versions of a number of Erd o s-Ko-Rado type theorems in extremal combinatorics, including the seminal complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the full' edge isoperimetric inequality, one relying on the Kruskal-Katona theorem. The edge isoperimetric inequality in the discrete cube specifies, for each pair of integers @math and @math , the minimum size @math of the edge boundary of an @math -element subset of @math ; the extremal families (up to automorphisms of the discrete cube) are initial segments of the lexicographic ordering on @math . We show that for any @math -element subset @math and any integer @math , if the edge boundary of @math has size at most @math , then there exists an extremal family @math such that @math , where @math is an absolute constant. This is best-possible, up to the value of @math . Our result can be seen as a stability' version of the edge isoperimetric inequality in the discrete cube, and as a discrete analogue of the seminal stability result of Fusco, Maggi and Pratelli concerning the isoperimetric inequality in Euclidean space.