Improved lower bounds on extremal functions of multidimensional permutation matrices

2015/06/28 by Jesse Geneson, Geneson, Jesse
Computer Science · Engineering · Mathematics · #05D99 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #cs.DM #graph theory and CDMA systems #math.CO #msc:05D99

paper · pdf · doi:10.48550/arxiv.1506.08447

8 pages

arxiv created 2015/06/28 · openalex publication_date 2015/06/28 · arxiv updated 2015/06/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

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 zeroes. Let f(n,P,d) denote the maximum number of ones in a d-dimensional n × ⋯ × n zero-one matrix that avoids P. Fox proved for n sufficiently large that f(n, P, 2) = 2^k^Θ(1)n for almost all k × k permutation matrices P. We extend this result by proving for d ≥ 2 and n sufficiently large that f(n, P, d) = 2^k^Θ(1)n^d-1 for almost all d-dimensional permutation matrices P of dimensions k × ⋯ × k.

Citations

• Forbidden paths and cycles in ordered graphs and matrices

Related

• Extremal Functions of Forbidden Multidimensional Matrices
• Forbidden formations in 0-1 matrices
• An upper bound on the number of high-dimensional permutations
• Better upper bounds on the Füredi-Hajnal limits of permutations
• Bounding extremal functions of forbidden 0-1 matrices using (r,s)-formations