« search calendars« Graduate Combinatorics Seminar

« An Important Graph

An Important Graph

September 26, 2018, 12:15 PM - 1:15 PM

Location:

Mathematics Graduate Student Lounge -- 7th Floor

Rutgers University

Hill Center

Mathematics Department

110 Frelinghuysen Road

Piscataway, NJ 08854

Aditya Potukuchi, Rutgers University

I will describe the construction of an explicit (family of) graph(s) due to Alon, which has many interesting and seemingly different extremal properties. Two of these that I will try to talk about are:
  1. Triangle free, but has small non-trivial eigenvalues (I will try to justify what "but" means here).
  2. Gives graph with a small Shannon capacity but a large theta value.
The topics that I will cover are strictly contained in this article: https://www.tau.ac.il/~nogaa/PDFS/ll70.pdf. There are, of course, interesting open problems related to these (I am not too familiar, but I will provide additional references for them) in case people find this interesting.