*********************************** * 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)