I was playing around with some new ideas earlier this week; that’s usually a sign that my research brain is swinging from asleep to awake and hollering. In this case, it was prompted by my having to proctor tests without any other diversion than a pen and a pad of paper. Anyhow, in my musings I came up with sort of a neat construction. Specifically, I figured out that every simple graph can be found as an induced subgraph of some Kneser graph.
What that means for those of you who don’t do this stuff for a living: I work with graphs, which are configurations of dots and lines. That’s not much of a definition, and so it admits quite a lot; any random, irregular collection of dots, with pairs either connected by a line or not, qualifies as a graph. An induced subgraph is what you get when you take a graph and only concentrate on a part of it: some collection of dots, and any lines only involving those dots. And a Kneser graph is a highly regular, symmetrical sort of structure.
And hence: any graph, any configuration of dots and lines – no matter how arbitrary it looks, no matter how irregular – can always be seen as a small part of something ordered and balanced. Contrariwise, highly structured configurations can, when looked at closely enough, be made up of the strangest things.
And I thought that was kind of cool.