2026-08-17T16:17:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7582 2024-03-12T11:58:23Z ddc:004 open_access

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques Brakensiek, Joshua extremal combinatorics independent sets isoperimetry stability The tensor power of the clique on t vertices (denoted by K_t^n) is the graph on vertex set {1, ..., t}^n such that two vertices x, y in {1, ..., t}^n are connected if and only if x_i != y_i for all i in {1, ..., n}. Let the density of a subset S of K_t^n to be mu(S) := |S|/t^n. Also let the vertex boundary of a set S to be the vertices of the graph, including those of S, which are incident to some vertex of S. We investigate two similar problems on such graphs. First, we study the vertex isoperimetry problem. Given a density nu in [0, 1] what is the smallest possible density of the vertex boundary of a subset of K_t^n of density nu? Let Phi_t(nu) be the infimum of these minimum densities as n -> infinity. We find a recursive relation allows one to compute Phi_t(nu) in time polynomial to the number of desired bits of precision. Second, we study given an independent set I of K_t^n of density mu(I) = (1-epsilon)/t, how close it is to a maximum-sized independent set J of density 1/t. We show that this deviation (measured by mu(I\J)) is at most 4 epsilon^{(log t)/(log t - log(t-1))} as long as epsilon < 1 - 3/t + 2/t^2. This substantially improves on results of Alon, Dinur, Friedgut, and Sudakov (2004) and Ghandehari and Hatami (2008) which had an O(epsilon) upper bound. We also show the exponent (log t)/(log t - log(t-1)) is optimal assuming n tending to infinity and epsilon tending to 0. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Brakensiek 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.33 urn:nbn:de:0030-drops-75828 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.33 eng https://creativecommons.org/licenses/by/3.0/legalcode