Signed permutations and the four color theorem

DOI10.1016/J.EXMATH.2009.04.002zbMATH Open1198.05046arXivmath/0606726OpenAlexW2055829777MaRDI QIDQ1034539FDOQ1034539

Shalom Eliahou, Cédric Lecouvey

Publication date: 6 November 2009

Published in: Expositiones Mathematicae (Search for Journal in Brave)

Abstract: To each permutation $sigma$ in $S_n$ we associate a triangulation of a fixed $(n+2)$-gon. We then determine the fibers of this association and show that they coincide with the sylvester classes depicted By Novelli, Hivert and Thibon. A signed version of this construction allows us to reformulate the four color theorem in terms of the existence of a signable path between any two permutations in the Cayley graph of the symmetric group $S_{n}.

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

zbMATH Keywords

signed permutationsfour color theoremsignable sequence of transpositionssigned diagonal flips

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Algebraic combinatorics (05E99) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Cites Work

• Cambrian lattices.
• Shellable Nonpure Complexes and Posets. I
• An analogue of the plactic monoid for binary search trees
• Signed diagonal flips and the four color theorem
• Flips signés et triangulations d'un polygone. (Signed flips and triangulations of a polygon)
• An algebraic approach to the planar coloring problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• On signed diagonal flip sequences
• Some properties of Bowlin and Brin's color graphs
• Mutation as metric on permutation group \(S_n\)
• Coloring planar graphs via colored paths in the associahedra
• Signed diagonal flips and the four color theorem

This page was built for publication: Signed permutations and the four color theorem

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