Extremal functions of forbidden multidimensional matrices

DOI10.1016/J.DISC.2017.08.017zbMATH Open1375.15046arXiv1506.03874OpenAlexW2963843359MaRDI QIDQ2404366FDOQ2404366

Jesse Geneson, Peter M. Tian

Publication date: 18 September 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

extremal functionpattern avoidancepermutation matrixzero-one matrix

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Saturation of Multidimensional 0-1 Matrices
• Almost all permutation matrices have bounded saturation functions
• Multivalued matrices and forbidden configurations
• Forbidden induced subposets of given height
• Title not available (Why is that?)
• A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
• Title not available (Why is that?)
• Forbidden formations in multidimensional 0-1 matrices
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Sequence saturation
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

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)