Multi-symbol forbidden configurations

DOI10.1016/J.DAM.2019.11.010MaRDI QIDQ2309548zbMATH OpenOpenAlexWikidataFDO

Authors Keaton Ellis, Baian Liu, Attila Sali

Publication date 1 April 2020

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

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

zbMATH Keywords

combinatoricsextremal graph theoryhypergraphsmultigraphsextremal set theoryforbidden configurations(0, 1)-matrices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Basic linear algebra (15A99) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: An $r$-matrix is a matrix with symbols in $0,1,dots,r-1$. A matrix is simple if it has no repeated columns. Let the support of a matrix $F$, $extsupp(F)$ be the largest simple matrix such that every column in $extsupp(F)$ is in $F$. For a family of $r$-matrices $mathcalF$, we define $extforb(m,r,mathcalF)$ as the maximum number of columns of an $m$-rowed, $r$-matrix $A$ such that $F$ is not a row-column permutation of $A$ for all $FinmathcalF$. While many results exist for $r=2$, there are fewer for larger numbers of symbols. We expand on the field of forbidding matrices with $r$-symbols, introducing a new construction for lower bounds of the growth of $extforb(m,r,mathcalF)$ (with respect to $m$) that is applicable to matrices that are either not simple or have a constant row. We also introduce a new upper bound restriction that helps with avoiding non-simple matrices, limited either by the asymptotic bounds of the support, or the size of the forbidden matrix, whichever is larger. Continuing the trend of upper bounds, we represent a well-known technique of standard induction as a graph, and use graph theory methods to obtain asymptotic upper bounds. With these techniques we solve multiple, previously unknown, asymptotic bounds for a variety of matrices. Finally, we end with block matrices, or matrices with only constant row, and give bounds for all possible cases.

Recommendations

• Multivalued matrices and forbidden configurations
• Small forbidden configurations
• General forbidden configuration theorems
• A survey of forbidden configuration results
• Forbidden configurations: boundary cases

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A survey of forbidden configuration results
• Forbidden configurations: Induction and linear algebra
• Forbidden families of configurations
• Large forbidden configurations and design theory
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Optimal multivalued shattering
• Small forbidden configurations
• Unavoidable traces of set systems

Cited in

(2)

• Multivalued matrices and forbidden configurations
• Exponential multivalued forbidden configurations

This page was built for publication: Multi-symbol forbidden configurations

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