Better upper bounds on the Füredi-Hajnal limits of permutations

DOI10.1137/1.9781611974782.150zbMATH Open1410.05014arXiv1607.07491OpenAlexW2558067245MaRDI QIDQ4575898FDOQ4575898

Authors: Josef Cibulka, Jan Kynčl 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: A binary matrix is a matrix with entries from the set $0,1$. We say that a binary matrix $A$ contains a binary matrix $S$ if $S$ can be obtained from $A$ by removal of some rows, some columns, and changing some $1$-entries to $0$-entries. If $A$ does not contain $S$, we say that $A$ avoids $S$. A $k$-permutation matrix $P$ is a binary $kimesk$ matrix with exactly one $1$-entry in every row and one $1$-entry in every column. The F"uredi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix $P$, there is a constant $c_P$ such that for every $ninmathbbN$, every $nimesn$ binary matrix $A$ with at least $c_{P}n$ $1$-entries contains $P$. We show that $c_{P}le{2}^{O(k^{2/3}lo{g}^{7/3}k/(loglogk{)}^{1/3})}$ asymptotically almost surely for a random $k$-permutation matrix $P$. We also show that $c_{P}le{2}^{(4+o(1))k}$ for every $k$-permutation matrix $P$, improving the constant in the exponent of a recent upper bound on $c_P$ by Fox. Moreover, we improve the upper bound on $c_P$ in terms of the Stanley-Wilf limit $s_P$ to $$. We also consider a higher-dimensional generalization of the Stanley-Wilf conjecture about the number of $d$-dimensional $n$-permutation matrices avoiding a fixed $d$-dimensional $k$-permutation matrix, and prove almost matching upper and lower bounds of the form $(2^k{)}^{O(n)}cdot(n!{)}^{d-1-1/(d-1)}$ and $n^{-O(k)}{k}^{Omega(n)}cdot(n!{)}^{d-1-1/(d-1)}$, respectively.

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

Recommendations

• On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Excluded permutation matrices and the Stanley-Wilf conjecture
• scientific article; zbMATH DE number 1504588
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Cited In (9)

• Almost all permutation matrices have bounded saturation functions
• On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
• Extremal functions of excluded tensor products of permutation matrices
• On an extremal problem for poset dimension
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• Universality of random permutations
• Twin-width II: small classes
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

This page was built for publication: Better upper bounds on the Füredi-Hajnal limits of permutations

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