License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.33
URN: urn:nbn:de:0030-drops-75828
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7582/
Brakensiek, Joshua
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques
Abstract
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.
BibTeX - Entry
@InProceedings{brakensiek:LIPIcs:2017:7582,
author = {Joshua Brakensiek},
title = {{Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {33:1--33:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7582},
URN = {urn:nbn:de:0030-drops-75828},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.33},
annote = {Keywords: extremal combinatorics, independent sets, isoperimetry, stability}
}
|
Keywords: |
|
extremal combinatorics, independent sets, isoperimetry, stability |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
