Extremal functions of forbidden multidimensional matrices

DOI10.1016/J.DISC.2017.08.017MaRDI QIDQ2404366zbMATH OpenOpenAlexFDO

Authors Peter M. Tian, Jesse Geneson

Publication date 18 September 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal functionpattern avoidancepermutation matrixzero-one matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Sign pattern matrices (15B35)

Abstract: Pattern avoidance is a central topic in graph theory and combinatorics. Pattern avoidance in matrices has applications in computer science and engineering, such as robot motion planning and VLSI circuit design. A $d$-dimensional zero-one matrix $A$ avoids another $d$-dimensional zero-one matrix $P$ if no submatrix of $A$ can be transformed to $P$ by changing some ones to zeros. A fundamental problem is to study the maximum number of nonzero entries in a $d$-dimensional $nimescdotsimesn$ matrix that avoids $P$. This maximum number, denoted by $f(n,P,d)$, is called the extremal function. We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on $f(n,P,d)$ when $n$ is large for every $d$-dimensional block permutation matrix $P$. We establish the tight bound $Theta(n^{d-1})$ on $f(n,P,d)$ for every $d$-dimensional tuple permutation matrix $P$. This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that $f(n,P,d)$ is super-homogeneous for a class of matrices $P$. We use this super-homogeneity to show that the limit inferior of the sequence $f(n,P,d)over{n}^{d-1}$ has a lower bound $2^{Omega(k^{1/d})}$ for a family of $kimescdotsimesk$ permutation matrices $P$. We also improve the upper bound on the limit superior from $2^{O(klogk)}$ to $2^{O(k)}$ for all $kimescdotsimesk$ permutation matrices and show that the new upper bound also holds for tuple permutation matrices.

Recommendations

• Extremal functions of forbidden double permutation matrices
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
• Forbidden formations in multidimensional 0-1 matrices
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Degrees of nonlinearity in forbidden 0-1 matrix problems

Cites work

• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• scientific article; zbMATH DE number 5204618 (Why is no real title available?)
• An Extremal Problem on Sparse 0-1 Matrices
• Combinatorics of Compositions and Words
• Combinatorics of permutations
• Davenport-Schinzel theory of matrices
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Extremal functions of excluded tensor products of permutation matrices
• Extremal functions of forbidden double permutation matrices
• On a problem of K. Zarankiewicz
• On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
• On linear forbidden submatrices
• Patterns in permutations and words.
• Rectilinear paths among rectilinear obstacles
• Some open problems on permutation patterns
• The maximum number of unit distances in a convex \(n\)-gon

Cited in

(12)

• On multi-dimensional patterns
• Almost all permutation matrices have bounded saturation functions
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Forbidden induced subposets of given height
• scientific article; zbMATH DE number 4092213 (Why is no real title available?)
• Sequence saturation
• Saturation of Multidimensional 0-1 Matrices
• Forbidden formations in multidimensional 0-1 matrices
• Multivalued matrices and forbidden configurations
• A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
• scientific article; zbMATH DE number 7673608 (Why is no real title available?)

This page was built for publication: Extremal functions of forbidden multidimensional matrices

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