Document Open Access Logo

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications

Authors Alexander Golovnev, Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.8.pdf
  • Filesize: 0.67 MB
  • 15 pages

Document Identifiers

Author Details

Alexander Golovnev
  • Georgetown University, Washington, DC, USA
Ishay Haviv
  • School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel

Funding

  • Golovnev, Alexander: Partially supported by a Rabin Postdoctoral Fellowship.
  • Haviv, Ishay: Research supported in part by the Israel Science Foundation (grant No. 1218/20).

Cite AsGet BibTex

Alexander Golovnev and Ishay Haviv. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.8

Abstract

The orthogonality dimension of a graph G = (V,E) over a field 𝔽 is the smallest integer t for which there exists an assignment of a vector u_v ∈ 𝔽^t with ⟨ u_v,u_v ⟩ ≠ 0 to every vertex v ∈ V, such that ⟨ u_v, u_{v'} ⟩ = 0 whenever v and v' are adjacent vertices in G. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant c such that for every sufficiently large integer t, it is NP-hard to decide whether the orthogonality dimension of an input graph over ℝ is at most t or at least 3t/2-c. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free n-vertex graphs whose complement has orthogonality dimension over the binary field at most n^{1-δ} for some constant δ > 0. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Circuit complexity
Keywords
  • Orthogonality dimension
  • minrank
  • rigidity
  • hardness of approximation
  • circuit complexity
  • chromatic number
  • Kneser graphs

Metrics

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

Related Versions

References

  1. Josh Alman and R. Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC'17), pages 641-652, 2017. Google Scholar
  2. Noga Alon. The Shannon capacity of a union. Combinatorica, 18(3):301-310, 1998. Google Scholar
  3. Noga Alon and Nabil Kahale. Approximating the independence number via the ϑ-function. Math. Program., 80:253-264, 1998. Google Scholar
  4. Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman. Round elimination in exact communication complexity. In Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'15), volume 44 of LIPIcs, pages 206-225, 2015. Google Scholar
  5. Jop Briët and Jeroen Zuiddam. On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination. Quantum Information & Computation, 17(1&2):106-116, 2017. Google Scholar
  6. Boris Bukh and Christopher Cox. On a fractional version of Haemers' bound. IEEE Trans. Inform. Theory, 65(6):3340-3348, 2019. Google Scholar
  7. Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC'19), pages 602-613, 2019. Google Scholar
  8. Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas J. Winter. On the quantum chromatic number of a graph. Electr. J. Comb., 14(1), 2007. Google Scholar
  9. Eden Chlamtáč and Ishay Haviv. Linear index coding via semidefinite programming. Combinatorics, Probability & Computing, 23(2):223-247, 2014. Preliminary version in SODA'12. Google Scholar
  10. Vasek Chvátal, Michael R. Garey, and David S. Johnson. Two results concerning multicoloring. Annals of Discrete Math., 2:151-154, 1978. Google Scholar
  11. Bruno Codenotti, Pavel Pudlák, and Giovanni Resta. Some structural properties of low-rank matrices related to computational complexity. Theor. Comput. Sci., 235(1):89-107, 2000. Preliminary version in ECCC'97. Google Scholar
  12. Ronald de Wolf. Quantum Computing and Communication Complexity. PhD thesis, Universiteit van Amsterdam, 2001. Google Scholar
  13. Tristan Denley. The odd girth of the generalised Kneser graph. Eur. J. Comb., 18(6):607-611, 1997. Google Scholar
  14. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. Preliminary version in STOC'06. Google Scholar
  15. Zeev Dvir and Benjamin L. Edelman. Matrix rigidity and the Croot-Lev-Pach lemma. Theory of Computing, 15(1):1-7, 2019. Google Scholar
  16. Zeev Dvir and Allen Liu. Fourier and circulant matrices are not rigid. In 34th Computational Complexity Conference (CCC'19), pages 17:1-17:23, 2019. Google Scholar
  17. Uriel Feige. Randomized graph products, chromatic numbers, and the Lovász ϑ-function. Combinatorica, 17(1):79-90, 1997. Preliminary version in STOC'95. Google Scholar
  18. Michael R. Garey and David S. Johnson. The complexity of near-optimal graph coloring. J. ACM, 23(1):43-49, 1976. Google Scholar
  19. Alexander Golovnev and Ishay Haviv. The (generalized) orthogonality dimension of (generalized) Kneser graphs: Bounds and applications. arXiv, 2020. URL: http://arxiv.org/abs/2002.08580.
  20. Alexander Golovnev, Oded Regev, and Omri Weinstein. The minrank of random graphs. IEEE Trans. Inform. Theory, 64(11):6990-6995, 2018. Preliminary version in RANDOM'17. Google Scholar
  21. Willem H. Haemers. On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(2):231-232, 1979. Google Scholar
  22. Ishay Haviv. On minrank and the Lovász theta function. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'18), pages 13:1-13:15, 2018. Google Scholar
  23. Ishay Haviv. Approximating the orthogonality dimension of graphs and hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS'19), pages 39:1-39:15, 2019. Google Scholar
  24. Ishay Haviv. On minrank and forbidden subgraphs. ACM Transactions on Computation Theory (TOCT), 11(4):20, 2019. Preliminary version in RANDOM'18. Google Scholar
  25. Ishay Haviv. Topological bounds on the dimension of orthogonal representations of graphs. Eur. J. Comb., 81:84-97, 2019. Google Scholar
  26. Sihuang Hu, Itzhak Tamo, and Ofer Shayevitz. A bound on the Shannon capacity via a linear programming variation. SIAM J. Discrete Math., 32(3):2229-2241, 2018. Preliminary version in ISIT'17. Google Scholar
  27. David R. Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246-265, 1998. Preliminary version in FOCS'94. Google Scholar
  28. Donald E. Knuth. The sandwich theorem. Electr. J. Comb., 1(A1):1-48, 1994. Google Scholar
  29. Michael Langberg and Alexander Sprintson. On the hardness of approximating the network coding capacity. IEEE Trans. Inform. Theory, 57(2):1008-1014, 2011. Preliminary version in ISIT'08. Google Scholar
  30. Abraham Lempel. Matrix factorization over GF(2) and trace-orthogonal bases of GF(2ⁿ). SIAM J. Comput., 4(2):175-186, 1975. Google Scholar
  31. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A, 25(3):319-324, 1978. Google Scholar
  32. László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1-7, 1979. Google Scholar
  33. László Lovász. Graphs and Geometry, volume 65. Colloquium Publications, 2019. Google Scholar
  34. László Lovász, Michael Saks, and Alexander Schrijver. Orthogonal representations and connectivity of graphs. Linear Algebra and its Applications, 114/115:439-454, 1989. Special Issue Dedicated to Alan J. Hoffman. Google Scholar
  35. Laura Mančinska and David E Roberson. Quantum homomorphisms. Journal of Combinatorial Theory, Series B, 118:228-267, 2016. Google Scholar
  36. René Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417-431, 1996. Google Scholar
  37. Søren Riis. Information flows, graphs and their guessing numbers. Electr. J. Comb., 14(1), 2007. Google Scholar
  38. Moshe Rosenfeld. Almost orthogonal lines in E^d. DIMACS Series in Discrete Math., 4:489-492, 1991. Google Scholar
  39. Giannicola Scarpa and Simone Severini. Kochen-Specker sets and the rank-1 quantum chromatic number. IEEE Trans. Inform. Theory, 58(4):2524-2529, 2012. Google Scholar
  40. Saul Stahl. n-tuple colorings and associated graphs. J. Comb. Theory, Ser. B, 20(2):185-203, 1976. Google Scholar
  41. Saul Stahl. The multichromatic numbers of some Kneser graphs. Discrete Mathematics, 185(1-3):287-291, 1998. Google Scholar
  42. Claude Tardif and Xuding Zhu. A note on Hedetniemi’s conjecture, Stahl’s conjecture and the Poljak-Rödl function. Electr. J. Comb., 26(4):P4.32, 2019. Google Scholar
  43. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th International Symposium on Mathematical Foundations of Computer Science (MFCS'77), pages 162-176, 1977. Google Scholar
  44. Marcin Wrochna and Stanislav Zivny. Improved hardness for H-colourings of G-colourable graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1426-1435, 2020. Google Scholar
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 Imprint Privacy Contact