Discrete mathematics

Speaker: 
Niko Nikov
Speaker Affiliation: 
UBC

November 2, 2021

Zoom - https://ubc.zoom.us/j/62676242229?pwd=RURtUC9UYXEweVZTMTNGT1EvY1FLZz09
Vancouver, BC V6T1Z2
Canada

View All Events

Abstract: 

The subject of forbidden configurations studies how large certain set families can be without containing a given configuration. The related concepts of shattering and VC-dimension have numerous applications in applied probability theory. In the language of $(0,1)$-matrices, we say that such a matrix is simple if it has no repeated columns. The matrix $A$ has $F$ as a configuration if $F$ is a row and column permutation of some submatrix of $A$. As with any problem in extremal combinatorics, we are interested in constructions and bounds. A 2018 result of Keevash provides lower bound constructions for matrices with no $t\cdot F$, the concatenation of $F$ with itself $t$ times. If $A$ is $m\times n$ with no $K_k$ (the matrix of all possible columns on $k$ rows), a well-known bound is $n\le \binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{k-1}$. We offer extensions $[K_k|F]$ to $K_k$ which preserve this bound, and discuss the variety of matrices achieving the bound.

Event Topic: