Bounds on parameters of minimally nonlinear patterns

MaRDI QIDQ1691099zbMATH OpenFDO

Authors P. A. CrowdMath

Publication date 15 January 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.00706, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p5

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

0-1 matricesextremal functionsgeneralized Davenport-Schinzel sequencesminimally non-linearordered graphspattern avoidance

Mathematics Subject Classification ID

Extremal combinatorics (05D99)

Abstract: Let $ex(n,P)$ be the maximum possible number of ones in any 0-1 matrix of dimensions $nimesn$ that avoids $P$. Matrix $P$ is called minimally non-linear if $ex(n,P)=omega(n)$ but $ex(n,P^{\prime })=O(n)$ for every strict subpattern $P^{\prime }$ of $P$. We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most $4$, and that a minimally non-linear 0-1 matrix with $k$ rows has at most $5k-3$ ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with $k$ rows. In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function $e{x}_{<}(n,G)$, which is the maximum possible number of edges in any ordered graph on $n$ vertices with no ordered subgraph isomorphic to $G$.

Review text

Summary: Let \(\mathrm{ex}(n, P)\) be the maximum possible number of ones in any 0-1 matrix of dimensions \(n \times n\) that avoids \(P\). Matrix \(P\) is called minimally non-linear if \(\mathrm{ex}(n, P) \neq O(n)\) but \(\mathrm{ex}(n, P') = O(n)\) for every proper subpattern \(P'\) of \(P\). We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most \(4\), and that a minimally non-linear 0-1 matrix with \(k\) rows has at most \(5k-3\) ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with \(k\) rows. In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function \(\operatorname{ex}_{<}(n, G)\), which is the maximum possible number of edges in any ordered graph on \(n\) vertices with no ordered subgraph isomorphic to \(G\).

Recommendations

• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• On linear forbidden submatrices
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• On 0-1 matrices and small excluded submatrices

Cites work

• A Combinatorial Problem Connected with Differential Equations
• Davenport-Schinzel theory of matrices
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Extremal functions of forbidden double permutation matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• scientific article; zbMATH DE number 1341912 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• The maximum number of unit distances in a convex n-gon
• The number of edges in k-quasi-planar graphs

Cited in

(7)

• On linear forbidden submatrices
• On the structure of matrices avoiding interval-minor patterns
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• MINIMAL FORBIDDEN PATTERNS OF MULTI-DIMENSIONAL SHIFTS
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Sequence saturation
• Almost all permutation matrices have bounded saturation functions

This page was built for publication: Bounds on parameters of minimally nonlinear patterns

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