Permutations in two dimensions that maximally separate neighbors

MaRDI QIDQ1740356zbMATH OpenFDO

Authors Mohammed Albow, Jeffrey Edgington, Petr Vojtěchovský, Mario A. Lopez

Publication date 30 April 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.04984, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p1

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

permutationtotal displacement

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: We characterize all permutations on even-by-even grids that maximally separate neighboring vertices. More precisely, let $n_1$, $n_2$ be positive even integers, let $I(n_1,n_2)=1,dots,n_{1}imes1,dots,n_2$ be the $n_{1}imes{n}_2$ grid, let $d$ be the $L_1$ metric on $I(n_1,n_2)$, and let $N=x,yinI(n_1,n_2)imesI(n_1,n_2):d(x,y)=1$ be the set of neighbors in $I(n_1,n_2)$. We characterize all permutations $pi$ of $I(n_1,n_2)$ that maximize $su{m}_{x,yinN}d(pi(x),pi(y))$.

Recommendations

• On \(k\)-neighbor separated permutations
• scientific article; zbMATH DE number 2192130
• Permutations in which pairs of numbers are not simultaneously close in position and close in size
• Permutations that separate close elements
• scientific article; zbMATH DE number 4204350

Cites work

• How permutations displace points and stretch intervals.
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• Interleaver properties and their applications to the trellis complexity analysis of turbo codes
• On computing the total displacement number via weighted Motzkin paths
• The generating function for total displacement

Cited in

(7)

• A duality for permutations
• Permutations that separate close elements
• scientific article; zbMATH DE number 4204350 (Why is no real title available?)
• The maximal length of a k-separator permutation
• On \(k\)-neighbor separated permutations
• scientific article; zbMATH DE number 2192130 (Why is no real title available?)
• Maximizing a sum related to image segmentation evaluation

This page was built for publication: Permutations in two dimensions that maximally separate neighbors

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