Local orthogonality dimension

DOI10.1002/JGT.22969zbMATH Open1522.05324arXiv2110.00718OpenAlexW3203207694MaRDI QIDQ6094036FDOQ6094036

Authors: Ishay Haviv 

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: An orthogonal representation of a graph $G$ over a field $mathbbF$ is an assignment of a vector $u_{v}inmathbb{F}^t$ to every vertex $v$ of $G$, such that $langle{u}_v,u_{v}angleeq0$ for every vertex $v$ and $langle{u}_v,u_{v^{\prime }}angle=0$ whenever $v$ and $v^{\prime }$ are adjacent in $G$. The locality of the orthogonal representation is the largest dimension of a subspace spanned by the vectors associated with a closed neighborhood in the graph. We introduce a novel graph parameter, called the local orthogonality dimension, defined for a given graph $G$ and a given field $mathbbF$, as the smallest possible locality of an orthogonal representation of $G$ over $mathbbF$. We investigate the usefulness of topological methods for proving lower bounds on the local orthogonality dimension. We prove that graphs for which topological methods imply a lower bound of $t$ on their chromatic number have local orthogonality dimension at least $lceilt/2ceil+1$ over every field, strengthening a result of Simonyi and Tardos on the local chromatic number. We show that for certain graphs this lower bound is tight, whereas for others, the local orthogonality dimension over the reals is equal to the chromatic number. More generally, we prove that for every complement of a line graph, the local orthogonality dimension over $mathbbR$ coincides with the chromatic number. This strengthens a recent result by Daneshpajouh, Meunier, and Mizrahi, who proved that the local and standard chromatic numbers of these graphs are equal. As another extension of their result, we prove that the local and standard chromatic numbers are equal for some additional graphs, from the family of Kneser graphs. We also show an $mathsfNP$-hardness result for the local orthogonality dimension and present an application of this graph parameter to the index coding problem from information theory.

Full work available at URL: https://arxiv.org/abs/2110.00718

Recommendations

• Topological bounds for graph representations over any field
• Topological bounds on the dimension of orthogonal representations of graphs
• On orthogonal representations of graphs
• Orthogonal representations over finite fields and the chromatic number of graphs
• Local chromatic number and distinguishing the strength of topological obstructions

zbMATH Keywords

minrankalgebraic topologylocal chromatic numberindex codinglocal orthogonality dimension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• Title not available (Why is that?)
• Coloring graphs with locally few colors
• Colorful subgraphs in Kneser-like graphs
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number, Ky Fan's theorem, and circular colorings
• On sets of vectors of a finite vector space in which every subset of basis size is a basis
• Topological lower bounds for the chromatic number: a hierarchy
• Approximating the independence number via the \(\vartheta\)-function
• Orthogonal representations over finite fields and the chromatic number of graphs
• Colourful theorems and indices of homomorphism complexes
• Index Coding With Side Information
• Topological bounds on the dimension of orthogonal representations of graphs
• Title not available (Why is that?)
• Nonlinear Index Coding Outperforming the Linear Optimum
• Colorings of complements of line graphs
• Title not available (Why is that?)
• Topological bounds for graph representations over any field
• Title not available (Why is that?)
• On the Hardness of Approximating the Network Coding Capacity
• \(H\)-wise independence
• Title not available (Why is that?)

Cited In (4)

• Orthogonality of elements with disjoint local spectrums
• Topological bounds for graph representations over any field
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Topological bounds on the dimension of orthogonal representations of graphs

This page was built for publication: Local orthogonality dimension

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