Do we have "higher order graphs"? Say, can we have graphs with vertices defined as edges of other graphs?
Is there any existing study on this?
Motivation:
Consider some graphs' embeddings, we can create curves whose endpoints are the graphs' embeddings' curves. If we think of this purely under graph theory, we get some sort of "higher order graphs". As we have higher-dimensional spaces in topology, why don't we study higher-order graphs? Or did we?
On
Sure, do what you like. In my graph theory final, we had to analyze the tree graph of a graph $G$, whose vertices are spanning trees of $G$ and whose vertices were connected iff the symmetric difference of their edge sets was a doubleton. So you can make the vertex set of a (finite) graph nearly anything finite that you can describe mathematically.
On
One way of thinking about the output of the Szemerédi regularity lemma for a given graph $G$ and a given $\epsilon>0$ is that it gives you a regularity graph for $G$, whose vertices are some collection of subsets $V_1,\cdots,V_k$ of vertices of $G$ and where two such vertices are joined by an edge if they are $\epsilon$-regular. The lemma tells you that all but $\epsilon k^2$ pairs of vertices in this graph are connected.
Then you can apply Turán's theorem to the regularity graph to arrive at a nice proof of the Erdős–Stone theorem.
On
I've found one example of higher-order graphs -- that is a graph formed via blocks.
Distinct blocks in a graph can have $\leq 1$ vertices in common, by that we can see blocks as "vertices" and the common vertices as "edges" between the block-formed vertices. For simple graphs, the block-formed graphs are also simple -- by "simple" I mean not multi-graph.
Sure! This is for example the situation with the Line graph, where each edge of a graph $G$ is a vertex in its line graph $L(G)$, and two vertices of $L(G)$ are connected iff the corresponding edges in $G$ have a common vertex.
This is very useful concept. See this wiki page for details.