The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications

DOI10.4230/LIPICS.CCC.2021.8MaRDI QIDQ6115359zbMATH OpenOpenAlexFDO

Authors Alexander Golovnev, Ishay Haviv

Publication date 12 July 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2021/14282/pdf/LIPIcs-CCC-2021-8.pdf/

zbMATH Keywords

chromatic numbercircuit complexityhardness of approximationKneser graphsminrankorthogonality dimensionrigidity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
• Approximating the orthogonality dimension of graphs and hypergraphs
• Approximating the orthogonality dimension of graphs and hypergraphs
• Topological bounds on the dimension of orthogonal representations of graphs
• Krausz dimension and its generalizations in special graph classes
• The independence number of the orthogonality graph in dimension 2ᵏ
• scientific article; zbMATH DE number 2115826
• A generalization of orthogonal factorizations in graphs
• A generalization of Kneser graphs
• On the diameter of generalized Kneser graphs

Cited in

(5)

• On the subspace choosability in graphs
• The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
• Approximating the orthogonality dimension of graphs and hypergraphs
• Approximating the orthogonality dimension of graphs and hypergraphs
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

This page was built for publication: The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115359)