Print Friendly printer friendly
 Events
Santiago Salazar
UBC
Tue 4 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127
Forbidden Berge hypergraphs
ESB 4127
Tue 4 Oct 2016, 4:00pm-5:00pm

Abstract

 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.
hide
Frank Sotille
TAMU
Thu 13 Oct 2016, 4:00pm
Discrete Math Seminar
Math 126
Math 126
Thu 13 Oct 2016, 4:00pm-5:00am

Abstract


hide
Gizem Karaali
Pomona College
Tue 18 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127
ESB 4127
Tue 18 Oct 2016, 4:00pm-5:00pm

Abstract


hide
Brian Chan
UBC
Tue 25 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127
ESB 4127
Tue 25 Oct 2016, 4:00pm-5:00pm

Abstract

 
hide
 
Top