Generalized graph theory

Question

This question may be kind of 'out there' but it got me thinking.

In graph theory we have a set of vertices $V$ and a set of edges $E$ which is made up of 2-element subsets of $V$ (either unordered or ordered).

Is there any notion in mathematics that considers a sort-of generalized graph, consisting of vertices $V$ and a set of 'edges' which is made up of, say, 3-element subsets of $V$ -- planes, instead of lines in the 2-element case. What about 'graphs' with 'edges' that are $n$-element subsets of $V$?

Does this notion even have any value?

Answer 1

It sounds like you may be interested in hypergraphs which is basically what you are asking about except edges can have any number of vertices associated with them. It turns out though that you can model hypergraphs with bipartite graphs. Say you have a bipartite graph with vertices coloured white and black, then a hypergraph can be associated with that by saying at the white vertices all the edges connected to that make the "hyperedge" and the black vertices would be the vertices of the hypergraph. If you have a hypergraph you can get a bipartite graph by adding the white vertices and splitting up the hyperedges into normal edges.

Answer 2

A simple graph $G(V, E)$ is a set of vertices and edges, where each edge $e \in E$ is defined as $e \subset V$ with $|e| = 2$.

A multigraph generalizes a simple graph, allowing for loops and multiple edges. A loop is an edge that is a one-element subset of $V$. As multiple edges are allowed, $E$ is a multiset of one and two element subsets of $V$.

The hypergraph further generalizes the multigraph, allowing for hyperedges $h$ simply to be $h \subset V$ and $h \neq \emptyset$.

Hypergraphs are incredibly useful in computational biology for modeling complex systems. There are also problems in hypergraphs that are computationally intractable, whereas in simple graphs the problem is quite simple. A good example is $2$-colorability. In simple graphs, it is easy to test if a graph is $2$-colorable, or bipartite. In a hypergrpah, we first have to define our coloring problem such that no hyperedge contains only vertices of one color. With this definition, checking if a hypergraph is $2$-colorable is $NP$-Complete. The proof deals with a probabilistic checkable proof. I actually wrote a paper for a class on this a while back, but I'm a tad rusty on the details.

There are still more general structures that generalize the concept of graphs in some sense, like matroids, for example.

Matroids generalize the concept of linear independence from linear algebra. Graph acyclicity shares this property, as does the property of three or more points being collinear on the Fano Plane. I wouldn't say that a Matroid generalizes the concept of a graph, specifically though.

Answer 3

If you're looking for a generalization of graphs that has a more geometric flavour, CW complexes come to mind.

http://en.wikipedia.org/wiki/CW_complex

A graph is a 1 dimensional CW complex. You have a discrete set of points, a set of line segments, and maps that attach the boundary of line segments to points (i.e. source and target).

However, CW complexes generalize to n dimensions. Here you could have a 2 dimensional complex that attaches the boundary of a higher order "edge" to "normal edges." Then the boundary of the boundaries would give you a set of "vertices."

CW complexes play a large role in homotopy theory.

Answer 4

It seems like the concept of hypergraphs fits exactly on what you're asking. There are still more general structures that generalize the concept of graphs in some sense, like matroids, for example.