CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department
Algorithms, Combinatorics and Optimization Seminar

For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University.

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...)


Huang Hao
Rutgers and IAS
Title: The minimum number of nonnegative edges in hypergraphs

Abstract: An r-unform n-vertex hypergraph H is said to have the Manickam–Miklós–Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. In this talk I will show that for n>10r3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight up to a constant factor. An immediate corollary of this result is the vector space Manickam–Miklós–Singhi conjecture which states that for n ≥ 4k and any weighting on the 1-dimensional subspaces of Fqn with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least ${n-1 \brack k-1}_q\ $. I will also discuss two additional generalizations, which can be regarded as analogues of the Erdős–Ko–Rado theorem on k-intersecting families.

Joint work with Benny Sudakov.

Date: Thursday, October 10, 2013
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Boris Bukh