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 Rn 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 √2(r−s)). Note that for s=0, we get random subgraphs of Kneser's graphs.