Orthogonal representations of random graphs

Combinatorics Seminar
Event time: 
Monday, October 8, 2018 - 4:00pm
LOM 201
Noga Alon
Speaker affiliation: 
Princeton University
Event description: 

An orthogonal representation of a graph $G$ is an assignment of a unit vector $x(v)$ in the $d$-dimensional Euclidean space $\mathbb{R}^d$ to every vertex $v$, so that for every two nonadjacent vertices $u$ and $v$, the corresponding vectors $x(u), x(v)$ are orthogonal.  Let $d(G)$ denote the minimum dimension $d$ for which such a representation exists.  This quantity and its analogs over other fields arise in the study of the Shannon capacity of $G$ and in the investigation of additional problems in Information Theory.  What is the typical value of $d(G)$ for the binomial random graph $G=G(n,0.5)$?  In recent work with Balla, Gishboliner, Mond and Mousset, we showed that the answer is $\Theta(n/log n)$. This settles a question of Knuth.  I will discuss the background of the question and outline the proof.

Research Area(s): 
Special note: 
This is an unusual meeting time