UBC

Tue 4 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127

Forbidden Berge hypergraphs

ESB 4127
Tue 4 Oct 2016, 4:00pm5: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 mrowed (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 vertexedge incidence matrix of a tree then bh(m,F) has a linear bound. When F is the vertexedge (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 mvertex graph avoiding K_{s,t} as a subgraph. Recent papers by Alon and others have solved some cases.
hide

TAMU

Thu 13 Oct 2016, 4:00pm
Discrete Math Seminar
Math 126


Math 126
Thu 13 Oct 2016, 4:00pm5:00am
Abstract
hide

Pomona College

Tue 18 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127


ESB 4127
Tue 18 Oct 2016, 4:00pm5:00pm
Abstract
hide

UBC

Tue 25 Oct 2016, 4:00pm
Discrete Math Seminar
ESB 4127


ESB 4127
Tue 25 Oct 2016, 4:00pm5:00pm
Abstract
hide

Seminar Information Pages
