Document Open Access Logo

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques

Author Joshua Brakensiek

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.33.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Joshua Brakensiek

Cite As Get BibTex

Joshua Brakensiek. Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.33

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.

Subject Classification

Keywords
  • extremal combinatorics
  • independent sets
  • isoperimetry
  • stability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, I. Dinur, E. Friedgut, and B. Sudakov. Graph Products, Fourier Analysis and Spectral Techniques. Geometric &Functional Analysis GAFA, 14(5):913-940, 2004. URL: http://dx.doi.org/10.1007/s00039-004-0478-3.
  2. Noga Alon and Joel H. Spencer. The Probabilistic Method. John Wiley &Sons, April 2004. Google-Books-ID: q3lUjheWiMoC. Google Scholar
  3. József Balogh and Dhruv Mubayi. A new short proof of a theorem of Ahlswede and Khachatrian. Journal of Combinatorial Theory, Series A, 115(2):326-330, February 2008. URL: http://dx.doi.org/10.1016/j.jcta.2007.03.010.
  4. S. Bobkov, C. Houdré, and P. Tetali. λ_∞, Vertex Isoperimetry and Concentration. Combinatorica, 20(2):153-172, February 2000. URL: http://dx.doi.org/10.1007/s004930070018.
  5. Béla Bollobás and Imre Leader. Compressions and isoperimetric inequalities. Journal of Combinatorial Theory, Series A, 56(1):47-62, January 1991. URL: http://dx.doi.org/10.1016/0097-3165(91)90021-8.
  6. Joshua Brakensiek. Vertex isoperimetry and independent set stability for tensor powers of cliques. arXiv:1702.04432 [cs, math], February 2017. arXiv: 1702.04432. URL: http://arxiv.org/abs/1702.04432.
  7. Joshua Brakensiek and Venkatesan Guruswami. New Hardness Results for Graph and Hypergraph Colorings. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:27, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.14.
  8. Demetres Christofides, David Ellis, and Peter Keevash. An Approximate Vertex-Isoperimetric Inequality for r-sets. The Electronic Journal of Combinatorics, 20(4):P15, August 2013. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p15.
  9. Irit Dinur and Ehud Friedgut. Intersecting Families Are Essentially Contained in Juntas. Comb. Probab. Comput., 18(1-2):107-122, March 2009. URL: http://dx.doi.org/10.1017/S0963548308009309.
  10. Irit Dinur, Ehud Friedgut, and Oded Regev. Independent Sets in Graph Powers are Almost Contained in Juntas. Geometric and Functional Analysis, 18(1):77-97, April 2008. URL: http://dx.doi.org/10.1007/s00039-008-0651-1.
  11. Irit Dinur and Samuel Safra. On the Hardness of Approximating Minimum Vertex Cover. Annals of Mathematics, 162(1):439-485, 2005. URL: http://www.jstor.org/stable/3597377.
  12. David Ellis, Gil Kalai, and Bhargav Narayanan. On symmetric intersecting families. arXiv:1702.02607 [math], February 2017. arXiv: 1702.02607. URL: http://arxiv.org/abs/1702.02607.
  13. David Ellis, Nathan Keller, and Noam Lifshitz. On the structure of subsets of the discrete cube with small edge boundary. arXiv:1612.06680 [math], December 2016. arXiv: 1612.06680. URL: http://arxiv.org/abs/1612.06680.
  14. David Ellis, Nathan Keller, and Noam Lifshitz. Stability versions of Erdős-Ko-Rado type theorems, via isoperimetry. arXiv:1604.02160 [math], April 2016. arXiv: 1604.02160. URL: http://arxiv.org/abs/1604.02160.
  15. David Ellis, Nathan Keller, and Noam Lifshitz. On a Biased Edge Isoperimetric Inequality for the Discrete Cube. arXiv:1702.01675 [math], February 2017. arXiv: 1702.01675. URL: http://arxiv.org/abs/1702.01675.
  16. David Ellis and Noam Lifshitz. On the union of intersecting families. arXiv:1610.03027 [math], October 2016. arXiv: 1610.03027. URL: http://arxiv.org/abs/1610.03027.
  17. Yuval Filmus. Ahlswede-Khachatrian Theorems: Weighted, Infinite, and Hamming. arXiv:1610.00756 [math], October 2016. arXiv: 1610.00756. URL: http://arxiv.org/abs/1610.00756.
  18. Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance Principle on the Slice. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:10, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.15.
  19. Yuval Filmus and Elchanan Mossel. Harmonicity and Invariance on Slices of the Boolean Cube. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.16.
  20. Ehud Friedgut. On the measure of intersecting families, uniqueness and stability. Combinatorica, 28(5):503-528, September 2008. URL: http://dx.doi.org/10.1007/s00493-008-2318-9.
  21. Mahya Ghandehari and Hamed Hatami. Fourier analysis and large independent sets in powers of complete graphs. Journal of Combinatorial Theory, Series B, 98(1):164-172, January 2008. URL: http://dx.doi.org/10.1016/j.jctb.2007.06.003.
  22. D. Greenwell and L. Lovász. Applications of product colouring. Acta Mathematica Academiae Scientiarum Hungarica, 25(3-4):335-340, September 1974. URL: http://dx.doi.org/10.1007/BF01886093.
  23. Andy Hammerlindl, John Bowman, and Tom Prince. Asymptote: The vector graphics language, 2014. Google Scholar
  24. A. J. W. Hilton and E. C. Milner. Some intersection theorems for systems of finite sets. The Quarterly Journal of Mathematics, 18:369-384, 1967. URL: http://dx.doi.org/10.1093/qmath/18.1.369.
  25. John D. Hunter. Matplotlib: A 2d Graphics Environment. Computing in Science &Engineering, 9(3):90-95, May 2007. URL: http://dx.doi.org/10.1109/MCSE.2007.55.
  26. Peter Keevash. Shadows and intersections: Stability and new proofs. Advances in Mathematics, 218(5):1685-1703, August 2008. URL: http://dx.doi.org/10.1016/j.aim.2008.03.023.
  27. Peter Keevash and Dhruv Mubayi. Set systems without a simplex or a cluster. Combinatorica, 30(2):175-200, March 2010. URL: http://dx.doi.org/10.1007/s00493-010-2401-x.
  28. Nathan Keller and Noam Lifshitz. On Large H-Intersecting Families. arXiv:1609.01884 [math], September 2016. arXiv: 1609.01884. URL: http://arxiv.org/abs/1609.01884.
  29. Nathan Keller and Noam Lifshitz. A tight stability version of the Complete Intersection Theorem. arXiv:1604.06135 [math], April 2016. arXiv: 1604.06135. URL: http://arxiv.org/abs/1604.06135.
  30. N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, July 1972. URL: http://dx.doi.org/10.1016/0097-3165(72)90019-2.
  31. Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, April 1972. URL: http://msp.org/pjm/1972/41-1/p21.xhtml.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact