Seminar

# The minimum number of nonnegative edges in hypergraphs

#### Graphs, Hypergraphs, and Computing

#### 03 April 14:00 - 15:00

#### Benjamin Sudakov - University of California, UCLA

Given an r-uniform n-vertex hypergraph H it is easy to see that one can always assign weights to its vertices with nonnegative sum, such that the number of edges whose total weight is nonnegative is at most the minimum degree of H. We say that H has the Manickam-Miklos-Singhi (MMS) property if for every weight assignment as above the number of nonnegative edges is at least the minimum degree of H.

In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight. One of the immediate corollaries of this result is the vector space Manickam-Miklos-Singhi conjecture from 1988 which determines the minimum number of nonnegative k-dimensional subspaces in any weighting of the 1-dimensional subspaces of (F_q)^n with nonnegative sum.

Joint work with Hao Huang.

In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight. One of the immediate corollaries of this result is the vector space Manickam-Miklos-Singhi conjecture from 1988 which determines the minimum number of nonnegative k-dimensional subspaces in any weighting of the 1-dimensional subspaces of (F_q)^n with nonnegative sum.

Joint work with Hao Huang.

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU