***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Igor Balla (ETH Zurich)
Thursday 19th September, 3:00 in Fine Hall 224.
Title: The minrank of random graphs over arbitrary fields
The minrank of a graph G on the set of vertices [n] over a field F is the
minimum possible rank of an n by n matrix M over F with nonzero diagonal
entries such that M_i,j = 0 whenever ij is not an edge of G. We show that
the minrank of the random graph G(n, p) over any field F is on the order of
n log(1/p) / log(n) with high probability. For the field of real numbers,
this settles a problem raised by Knuth in 1994. The proof combines a recent
argument of Golovnev, Regev, and Weinstein, who proved the above result for
finite fields of size at most n^O(1), with tools from linear algebra,
including an estimate of Rónyai, Babai, and Ganapathy for the number of
zero-patterns of a sequence of polynomials.
Joint work with Noga Alon, Lior Gishboliner, Adva Mond, and Frank Mousset.
----------------------------------
Next week: No talk. Week after Fan Chung.
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)