Suitable sets of permutations, packings of triples, and Ramsey's theorem

DOI10.1016/J.EJC.2019.103021MaRDI QIDQ2011141zbMATH OpenOpenAlexFDO

Authors Xian De Zhang

Publication date 28 November 2019

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

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

zbMATH Keywords

nonexistenceextremal problemRamsey's theoremsuitable arraysuitable core

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05) Ramsey theory (05D10)

Abstract: A set of $N$ permutations of $1,2,ldots,v$ is $t$-suitable, if each symbol precedes each subset of $t-1$ others in at least one permutation. The extremal problem of determining the smallest size $N$ of such sets for given $v$ and $t$ was the subject of classical studies by Dushnik in 1950 and Spencer in 1971. Colbourn recently introduced the concept of suitable cores as equivalent objects of suitable sets of permutations, and studied the dual problem of determining the largest $v=extSCN(t,N)$ such that a suitable core exists for given $t$ and $N$. Chan and Jedwab showed that when $N=lfloorfract+12floorlceilfract+12ceil+l$, the value of SCN$(t,N)$ is asymptotically $lfloorfract2floor+2$ if $l$ is a fixed integer. In this paper, we improve this result by showing that it is also true when $l=O(lnt)$ using Ramsey theory. When $v$ is bigger than $lfloorfract2floor+2$, we give new explicit constructions of suitable cores from packings of triples, and random constructions from extended Ramsey colorings.

Recommendations

• Constructions and nonexistence results for suitable sets of permutations
• Suitable permutations, binary covering arrays, and Paley matrices
• An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements
• Set systems and families of permutations with small traces
• Scrambling permutations and entropy of hypergraphs

Cites work

• scientific article; zbMATH DE number 124521 (Why is no real title available?)
• A class of three-designs
• A review of the available construction methods for Golomb rulers
• A survey of binary covering arrays
• Asymptotic determination of the last packing number of quadruples
• Combinatorial Relations and Chromatic Graphs
• Concerning a Certain Set of Arrangements
• Constructions and nonexistence results for suitable sets of permutations
• Hadamard matrices and their applications
• Largest minimal inversion-complete and pair-complete sets of permutations
• Minimal scrambling sets of simple orders
• New lower bound formulas for multicolored Ramsey numbers
• New lower bounds for some multicolored Ramsey numbers
• On Orthogonal Matrices
• On Quadruple Systems
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On a packing and covering problem
• On the dimensions of ordered sets of bounded degree
• On the order dimension of 1-sets versus k-sets
• Recent developments in graph Ramsey theory
• Some remarks on the theory of graphs
• Suitable permutations, binary covering arrays, and Paley matrices
• The completion determination of optimal \((3,4)\)-packings

Cited in

(2)

• Suitable permutations, binary covering arrays, and Paley matrices
• Constructions and nonexistence results for suitable sets of permutations

This page was built for publication: Suitable sets of permutations, packings of triples, and Ramsey's theorem

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