On the X-rays of permutations

DOI10.1016/J.ENDM.2005.05.063MaRDI QIDQ3439186zbMATH OpenOpenAlexFDO

Authors Cecilia Bebeacua, Toufik Mansour, Alex Postnikov, Simone Severini

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationsscore sequences of tournamentsX-rayszero-sum arrays

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20)

Abstract: The X-ray of a permutation is defined as the sequence of antidiagonal sums in the associated permutation matrix. X-rays of permutation are interesting in the context of Discrete Tomography since many types of integral matrices can be written as linear combinations of permutation matrices. This paper is an invitation to the study of X-rays of permutations from a combinatorial point of view. We present connections between these objects and nondecreasing differences of permutations, zero-sum arrays, decomposable permutations, score sequences of tournaments, queens' problems and rooks' problems.

Recommendations

• Hankel and Toeplitz X-rays of permutations
• The X-class and almost-increasing permutations
• X-rays characterizing some classes of discrete sets
• \(L\)-rays of permutation matrices and doubly stochastic matrices
• Permutation matrices, their discrete derivatives and extremal properties

Cites work

• Arrays and brooks
• Discrete tomography. Foundations, algorithms, and applications
• Handbook of Graph Theory
• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• On the computational complexity of reconstructing lattice sets from their X-rays
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• Reconstructing permutation matrices from diagonal sums

Cited in

(10)

• \(L\)-rays of permutation matrices and doubly stochastic matrices
• Geometry of paired comparisons
• Hankel and Toeplitz X-rays of permutations
• Perfect Skolem sets
• Counting staircases in integer compositions
• scientific article; zbMATH DE number 7350756 (Why is no real title available?)
• scientific article; zbMATH DE number 7529808 (Why is no real title available?)
• Hook length and symplectic content in partitions
• The X-class and almost-increasing permutations
• On the number of transversals in Cayley tables of cyclic groups

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the X-rays of permutations

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