Exponential multivalued forbidden configurations

DOI10.46298/DMTCS.6613MaRDI QIDQ4987274zbMATH OpenOpenAlexWikidataFDO

Authors Travis Dillon, Attila Sali

Publication date 3 May 2021

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.16305, https://dmtcs.episciences.org/7283

zbMATH Keywords

\((0, 1)\)-matricesextremal set theoryforbidden configurations

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05)

Abstract: The forbidden number $mathrmforb(m,F)$, which denotes the maximum number of unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is a row and column permutation of $F$, has been widely studied in extremal set theory. Recently, this function was extended to $r$-matrices, whose entries lie in $0,1,dots,r-1$. The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many $(0,1)$-matrices $F$, including all $2$-rowed matrices when $r>3$. We also prove a stability result for the $2imes2$ identity matrix. Along the way, we expose some interesting qualitative differences between the cases $r=2$, $r=3$, and $r>3$.

Recommendations

• Multivalued matrices and forbidden configurations
• Small forbidden configurations. IV: The 3 rowed case
• Small forbidden configurations
• A survey of forbidden configuration results
• Multi-symbol forbidden configurations

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A survey of forbidden configuration results
• scientific article; zbMATH DE number 3887691 (Why is no real title available?)
• Multi-symbol forbidden configurations
• On the density of families of sets
• On the density of sets of vectors
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Optimal multivalued shattering
• Small forbidden configurations

Cited in

(1)

• Multivalued matrices and forbidden configurations

This page was built for publication: Exponential multivalued forbidden configurations

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