Coloring random subgraphs of some distance graphs
Speaker:
Andrei Raigorodskii, Moscow Institute of Physics and Technology
Date and Time:
Monday, June 19, 2017 - 10:00am to 10:30am
Location:
Fields Institute, Stewart Library
Abstract:
In my talk, I will speak about the chromatic numbers of random subgraphs of some graphs, whose vertices are $ (0,1) $-vectors in $ {\mathbb R}^n $ with exactly $ r $ non-zero coordinates and whose edges are drawn between some two vertices, if and only if the inner product of the corresponding vectors equals $ s $ (so that the distance between them is $ \sqrt{2(r-s)} $). Note that for $ s = 0 $, we get random subgraphs of Kneser's graphs.