A simple proof of a theorem of Schmerl and Trotter for permutations

DOI10.4310/JOC.2015.V6.N1.A3zbMATH Open1312.05004arXiv1409.4725MaRDI QIDQ2345765FDOQ2345765

Authors: Robert Brignall, Vincent Vatter 

Publication date: 20 May 2015

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: When specialized to the context of permutations, Schmerl and Trotter's Theorem states that every simple permutation which is not a parallel alternation contains a simple permutation with one fewer entry. We give an elementary proof of this result.

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

Recommendations

• A Simple Proof of a Theorem of Schur
• A simple proof for Schur's theorem
• A simple proof of Schmidt's conjecture
• A combinatorial proof of a result for permutation pairs
• A constructive proof of a permutation-based generalization of Sperner's lemma
• scientific article; zbMATH DE number 1305365
• A proof of Niederreiter's rearrangement theorem
• scientific article; zbMATH DE number 5230613

zbMATH Keywords

Schmerl and Trotter theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (3)

• Symmetric maximal Condorcet domains
• Labelled well-quasi-order for permutation classes
• Letter graphs and modular decomposition

Uses Software

• PermLab

This page was built for publication: A simple proof of a theorem of Schmerl and Trotter for permutations

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