The three-permutations problem

DOI10.1016/0012-365X(90)90334-EMaRDI QIDQ908913zbMATH OpenOpenAlexFDO

Authors Peter Fishburn, William V. Gehrlein

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90334-e

zbMATH Keywords

three-permutation problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Review text

Given a set \(N=\{1,2,3,...,n\}\) and any three permutations on it, it is desired to choose f: \(N\to \{-1,1\}\) in such a way so as to minimize the maximum of absolute partial sum of f values. The three-permutation problem is to obtain the supremum of this minimum. Nothing is known about this supremum except that it is greater than or equal to 2. In this paper the authors consider a special case of this problem in which the maximum absolute partial sum for one of the three permutations is 1. It is shown that for this special case the supremum is unbounded.

Recommendations

• Scrambling permutations and entropy of hypergraphs
• On the discrepancy of 3 permutations
• scientific article; zbMATH DE number 26585
• On one extremal problem for numerical series
• Permutations with small maximal \(k\)-consecutive sums

Cites work

• Balanced two-colorings of finite sets in the square. I
• Discrepancy of set-systems and matrices
• scientific article; zbMATH DE number 3823797 (Why is no real title available?)
• Roth's estimate of the discrepancy of integer sequences is nearly sharp

Cited in

(6)

• A note on ternary sequences of strings of 0 and 1
• On a property of a three-dimensional matrix
• On reverse-free codes and permutations
• scientific article; zbMATH DE number 4031768 (Why is no real title available?)
• scientific article; zbMATH DE number 7106992 (Why is no real title available?)
• On one extremal problem for numerical series

This page was built for publication: The three-permutations problem

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