Improved lower bounds on extremal functions of multidimensional permutation matrices

MaRDI QIDQ6263093zbMATH OpenFDO

Authors Jesse Geneson

Publication date 28 June 2015

Mathematics Subject Classification ID

Extremal combinatorics (05D99)

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 $nimescdotsimesn$ zero-one matrix that avoids $P$. Fox proved for $n$ sufficiently large that $f(n,P,2)=2^{k^{Theta(1)}}n$ for almost all $kimesk$ permutation matrices $P$. We extend this result by proving for $dgeq2$ and $n$ sufficiently large that $f(n,P,d)=2^{k^{Theta(1)}}{n}^{d-1}$ for almost all $d$-dimensional permutation matrices $P$ of dimensions $kimescdotsimesk$.

This page was built for publication: Improved lower bounds on extremal functions of multidimensional permutation matrices

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