Complexes, Graphs, Homotopy and Shannon Capacity

Some remarks:
- The topics appear a bit inhomogenous. Indeed, it is. But all themes relate to connection graphs. Especially, Shannon capacity and graph homotopy seem have nothing in common at first. But there is a relation: Claude Shannon (graph arithmetic and capacity) and George W. Whitehead (homotopy) both worked at MIT and both lived in Winchester, MA!
- For the Szpilrajn-Marczewski theorem, the best effective bound on the size of the union of sets in G was given by Erdoes, Goodman and Posa in 1964. It is [n^2/4]. In our case, the graphs have |G| vertices and the union of all sets in G has a cardinality which is the independence number, much smaller than the Erdoes-Goodman-Posa upper bound. The relation between graphs and their generating set of sets is especially elegant in the connection graph case.
- Connection graphs are also extreme with respect to Shannon capacity. In the information theoretical set-up, the graph encodes the the error relations which can happen between letters in an alphabet. For connection graphs, we do not gain any communication capacity by using powers of the graph. The Shannon Capacity is equal to the independence number. This is quite special and related that if we take graph powers, this comes from Cartesian product powers for the simplicial complexes. Indeed the strong product of connection graphs is the connection graph of the Cartesian product.
- in the Chen-Yau-Yee paper of 2001, a report of M.H. Graham from 1979 is mentioned which did already some graph homotopy then (I could not get hold of the Graham report yet). As it is such a natural notion, it might have been developed independently many times. There are other homotopy notions like Babson-Barcelo-Longueville-Laubenbacher which mimic the definition from the continuum and requires to look at graph products. I myself always used the simple one with vertices and used it first in a paper with Frank Josellis when working on Ljusternik Schnirelmann category for graphs (the result is the same in the continuum as in graph theory but in graph theory lives within combinatorics and finite mathematics). There are also approaches to homotopy which use geometric realizations but this leaves combinatorics and so finite mathematics.
- The Lovasz number is very much related to the fact that the connection Laplacians (defined for an arbitrary energy) multiply as tensor products when taking strong products. Taking the tensor products of the umbrellas produces umbrellas of the strong product. This is the reason for the upper bound as tensor products are compatible with the Shannon strong product. The fact that the strong product for connection graphs produces multi-particle pictures brings the story also closer to quantum mechanics and is a reason why Shannon capacity is of interest in quantum computing.
A detail about the presentation a typo: at the end of my presentation when building the Lovasz umbrella U for a connection graph of course the dot products u(x). u(y) =0 if x and y do not intersect. This is the the case when (x,y) is not an edge in the connection graph (I see that there was a not-equal sign on the board). By the way, the beautiful umbrella picture origins from the original paper of Lovasz of 1979. The story is well told in the little AMS book "33 miniatures" by J. Matousek, where I myself first learnt it originally and where the expression Lovasz umbrella appears). The original paper of Shannon from 1956 is very good too as well as a very accessible paper by Donald Knuth from 1994 named "The Sandwich theorem".