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

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)

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

• scientific article; zbMATH DE number 1943970 (Why is no real title available?)
• Binomial edge ideals and conditional independence statements
• Graded syzygies
• Gröbner bases in commutative algebra
• 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

(17)

• Orthogonal representations and connectivity of graphs
• Cohen-Macaulay binomial edge ideals and accessible graphs
• The universal Gröbner basis of a binomial edge ideal
• scientific article; zbMATH DE number 7692355 (Why is no real title available?)
• Hilbert-Poincaré series of parity binomial edge ideals and permanental ideals of complete graphs
• Regularity of powers of (parity) binomial edge ideals
• Comparison of symbolic and ordinary powers of parity binomial edge ideals
• Generically globally rigid graphs have generic universally rigid frameworks
• Parity binomial edge ideals
• Regularity of parity binomial edge ideals
• Orthogonal embeddings of graphs in Euclidean space
• Positive matching decompositions of graphs
• Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties
• Hypergraph LSS-ideals and coordinate sections of symmetric tensors
• Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs
• When are the natural embeddings of classical invariant rings pure?
• Binomial edge ideals of bipartite 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)