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

DOI10.1016/J.EJC.2019.103021zbMATH Open1428.05012arXiv1808.03159OpenAlexW2974718550MaRDI QIDQ2011141FDOQ2011141

Authors: Xian De Zhang 

Publication date: 28 November 2019

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

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.

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

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

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)

Cites Work

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

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)