On the ideal of orthogonal representations of a graph in R^2

DOI10.1016/J.AAM.2015.09.009zbMATH Open1322.05098arXiv1411.3674OpenAlexW1727313991MaRDI QIDQ745075FDOQ745075

Authors: Jürgen Herzog, Antonio Macchia, Sara Saeedi Madani, Volkmar Welker 

Publication date: 13 October 2015

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: In this paper, we study orthogonal representations of simple graphs $G$ in $mathbb{R}^d$ from an algebraic perspective in case $d=2$. Orthogonal representations of graphs, introduced by Lov'asz, are maps from the vertex set to $mathbb{R}^d$ where non-adjacent vertices are sent to orthogonal vectors. We exhibit algebraic properties of the ideal generated by the equations expressing this condition and deduce geometric properties of the variety of orthogonal embeddings for $d=2$ and $mathbbR$ replaced by an arbitrary field. In particular, we classify when the ideal is radical and provide a reduced primary decomposition if $sqrt-1otinK$. This leads to a description of the variety of orthogonal embeddings as a union of varieties defined by prime ideals. In particular, this applies to the motivating case $K=mathbbR$.

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

Recommendations

• On orthogonal representations of graphs
• Orthogonal representations and connectivity of graphs
• Topological bounds on the dimension of orthogonal representations of graphs
• Orthonormal representations of \(H\)-free graphs
• Orthogonal representations, minimum rank, and graph complements
• A correction: Orthogonal representations and connectivity of graphs
• Orthogonality graphs of real Cayley-Dickson algebras. II: The subgraph on pairs of basis elements
• Orthogonal embeddings of graphs in Euclidean space
• Orthogonal representations over finite fields and the chromatic number of graphs
• Orthogonal graphs of characteristic 2 and their automorphisms

zbMATH Keywords

primary decompositionradical idealorthogonal representation of graphspermanental edge ideal

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Graph representations (geometric and intersection representations, etc.) (05C62) Algebraic combinatorics (05E99) Dimension theory, depth, related commutative rings (catenary, etc.) (13C15)

Cites Work

• On the Shannon capacity of a graph
• Graded syzygies
• Gröbner bases in commutative algebra
• Monomial and toric ideals associated to Ferrers graphs
• Orthogonal representations and connectivity of graphs
• Title not available (Why is that?)
• Binomial edge ideals and conditional independence statements
• Permanental ideals

Cited In (17)

• Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties
• Positive matching decompositions of graphs
• The universal Gröbner basis of a binomial edge ideal
• Hilbert-Poincaré series of parity binomial edge ideals and permanental ideals of complete graphs
• Orthogonal representations and connectivity of graphs
• Regularity of parity binomial edge ideals
• Orthogonal embeddings of graphs in Euclidean space
• Hypergraph LSS-ideals and coordinate sections of symmetric tensors
• Cohen-Macaulay binomial edge ideals and accessible graphs
• Parity binomial edge ideals
• Generically globally rigid graphs have generic universally rigid frameworks
• Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs
• Title not available (Why is that?)
• Comparison of symbolic and ordinary powers of parity binomial edge ideals
• Binomial edge ideals of bipartite graphs
• When are the natural embeddings of classical invariant rings pure?
• Regularity of powers of (parity) binomial edge ideals

Uses Software

• Macaulay2

This page was built for publication: On the ideal of orthogonal representations of a graph in \(\mathbb{R}^2\)

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