Discrete Math Seminar: Santiago Salazar

Given two matrices A,B we say that A is a Berge hypergraph of B if there is a submatrix of B, say matrix D, and a row and column permutation of A, say matrix C, so that C=D. Define Av(m,F) to be the set of all m-rowed (0,1)-matrices with no repeated columns and no Berge hypergraph F. Define Bh(m,F) to be the maximum, over all matrices A in Av(m,F), of the number of columns of A. We are interested in determining the asymptotic growth of Bh(m,F) for specific F. We show some techniques we can use to this end and mention the general results determined for F with 5 or fewer rows. We also show that if F is the vertex-edge incidence matrix of a tree then bh(m,F) has a linear bound. When F is the vertex-edge (s+t)x(st) incidence matrix of the bipartite graph K_{s,t} we show that finding Bh(m,F) relates to determining ex(m,K_r,K_{s,t} ), the maximum number of complete subgraphs K_r in a m-vertex graph avoiding K_{s,t} as a subgraph. Recent papers by Alon and others have solved some cases.