Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 28, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Heidi Gebauer
We say that a given k-uniform hypergraph is non-two-colorable if every red/blue-coloring of its vertices yields an edge where all vertices have the same color. It is a long-standing open problem to determine the minimum number m(k) such that there exists a non-2-colorable k-uniform hypergraph with m(k) hyperedges. Erdos showed, using the probabilistic method, that m(k) <= O(k^2 * 2^k), and by a result of Radhakrishnan and Srinivasan, m(k) >= \Omega(\sqrt(k/ln k) 2^k). These are the best known bounds. This talk will be about an explicit construction of a non-two-colorable hypergraph with 2^(k(1+o(1)) edges.
Automatic MiSe System Software Version 1.4803M | admin login