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:
- Triangle free, but has small non-trivial eigenvalues (I will try to justify what "but" means here).
- 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.
|
