Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Special Combinatorics Seminar

Sebastian Cioaba

UCSD

Covering hypergraphs with cuts

Abstract:

Covering a graph with subgraphs of certain type has a long history in graph theory and it goes back to Boole, Ore and M.Hall. The problem of covering a graph by cliques or bicliques has been studied by many researchers including Erdos, Goodman, Posa, Chung, Graham, Pollak, Alon etc. Few of the results obtained for graphs extend to hypergraphs. In this talk, I will present some of these results and show some new results regarding the covers of an $r$-uniform hypergraph by $k$-cuts such that the total size of the cuts (the sum of the number of edges of all cuts) is minimum. This is joint work with Andr$\rm\acute e$ K$\rm\ddot u$ndgen (Cal.State San Marcos).

December 7, 2006

1:30 PM

AP&M 6402

****************************