Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Speaker: | Hao Huang |
---|---|
Affiliation: | Institute for Advanced Study and DIMACS |
Room: | Mathematics and Computer Building (MC) 5158 |
Extremal combinatorics studies the maximum or minimum possible size of a combinatorial structure satisfying certain properties. In this talk I will briefly review some recent developments in this field and connections with other areas, and focus on the following extremal problem. A hypergraph H is said to have the MMS property if for every assignment of weights to its vertices with non-negative sum, the number of edges whose total weight is non-negative is at least the minimum degree of H. We show that all sufficiently large hypergraphs with equal codegrees have the MMS property. Our result resolves a long-standing conjecture by Manickam, Miklos, and Singhi, which states that for $n>4k$ and any weighting on the 1-dimensional subspaces of F_q^n with non-negative sum, the number of non-negative k-dimensional subspaces is at least n-1 k-1. Joint work with Benny Sudakov.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.