Name
Abstract | ||
|---|---|---|
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 {1, ..., t}^n$ are connected if and only if $x_i neq y_i$ for all $i {1, ..., n}$. Let the density of a subset $S$ of $K_t^n$ be $mu(S) := frac{|S|}{t^n}$, and let the vertex boundary of a set $S$ be vertices which are incident some vertex of $S$, perhaps including points of $S$. We investigate two similar problems on such graphs. First, we study the vertex isoperimetry problem. Given a density $nu [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 to infty$. We find a recursive relation allows one compute $Phi_t(nu)$ in time polynomial the number of desired bits of precision. Second, we study given an independent set $I subseteq K_t^n$ of density $mu(I) = frac{1}{t}(1-epsilon)$, how close it is a maximum-sized independent set $J$ of density $frac{1}{t}$. We show that this deviation (measured by $mu(I setminus J)$) is at most $4epsilon^{frac{log t}{log t - log(t-1)}}$ as long as $epsilon u003c 1 - frac{3}{t} + frac{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 $frac{log t}{log t - log(t-1)}$ is optimal assuming $n$ tending infinity and $epsilon$ tending $0$. methods have similarity 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. |
Year | Venue | DocType |
|---|---|---|
2017 | APPROX-RANDOM | Conference |
Volume | Citations | PageRank |
abs/1702.04432 | 0 | 0.34 |
References | Authors | |
5 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joshua Brakensiek | 1 | 2 | 6.80 |