Bounding extremal functions of forbidden 0-1 matrices using (r,s)-formations

2016/03/19 by Jesse Geneson, Meghal Gupta, Geneson, Jesse +1
Computer Science · Mathematics · #05D99 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05D99

paper · pdf · doi:10.48550/arxiv.1603.06124

10 pages

arxiv created 2016/03/19 · arxiv updated 2016/03/22

Abstract

First, we prove tight bounds of n 2^(1)/((t-2)!)α(n)^t-2 ± O(α(n)^t-3) on the extremal function of the forbidden pair of ordered sequences (1 2 3 … k)^t and (k … 3 2 1)^t using bounds on a class of sequences called (r,s)-formations. Then, we show how an analogous method can be used to derive similar bounds on the extremal functions of forbidden pairs of 0-1 matrices consisting of horizontal concatenations of identical identity matrices and their horizontal reflections.

Related

• Forbidden formations in 0-1 matrices
• Extremal Functions of Forbidden Multidimensional Matrices
• On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
• On Forbidden Submatrices
• Forbidden Families of Minimal Quadratic and Cubic Configurations