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

DOI10.1016/J.AAM.2015.09.009MaRDI QIDQ745075zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

orthogonal representation of graphspermanental edge idealprimary decompositionradical ideal

Mathematics Subject Classification ID

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

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$.

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

Cites work

• Binomial edge ideals and conditional independence statements
• Graded syzygies
• Gröbner bases in commutative algebra
• scientific article; zbMATH DE number 1943970 (Why is no real title available?)
• Monomial and toric ideals associated to Ferrers graphs
• On the Shannon capacity of a graph
• Orthogonal representations and connectivity of graphs
• Permanental ideals

Cited in

(23)

• Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties
• Binomial edge ideals of bipartite graphs
• Orthogonal representations and connectivity of graphs
• Cohen-Macaulay binomial edge ideals and accessible graphs
• Positive matching decompositions of graphs
• Generically globally rigid graphs have generic universally rigid frameworks
• Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs
• The universal Gröbner basis of a binomial edge ideal
• Regularity of powers of (parity) binomial edge ideals
• Regularity of parity binomial edge ideals
• Orthogonal embeddings of graphs in Euclidean space
• scientific article; zbMATH DE number 7692355 (Why is no real title available?)
• When are the natural embeddings of classical invariant rings pure?
• Hypergraph LSS-ideals and coordinate sections of symmetric tensors
• Comparison of symbolic and ordinary powers of parity binomial edge ideals
• F-purity of binomial edge ideals
• Permanental ideals of symmetric matrices
• On positive matching decomposition conjectures of hypergraphs
• Normality, factoriality and strong F-regularity of Lovász-Saks-Schrijver rings
• Gröbner basis and Krull dimension of the Lovász-Saks-Sherijver ideal associated to a tree
• (Almost) complete intersection Lovász-Saks-Schrijver ideals and the regularity of their powers
• Parity binomial edge ideals
• Hilbert-Poincaré series of parity binomial edge ideals and permanental ideals of complete graphs

Describes a project that uses

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)