Hypergraphs

From CanisiusmathWiki

A hypergraph is a generalization of a graph, in that it consists of a set of vertices and a set of collections of those vertices, called edges. In a hypergraph, however, an edge need not contain merely two vertices.

As in graphs, the degree of a hypergraph's vertex is the number of edges in which it is included. Note, however, that as for hypergraphs the degree is not necessarily equal to the number of neighbors of a particular vertex, some theorems about the degree of a graph break down at the level of hypergraphs.

A hypergraph is regular of degree r if each vertex is of degree r. A hypergraph is k-uniform if each edge contains exactly k vertices. A k-partite hypergraph is one in which the edges select at most one vertex from each of k partitions of the vertex set - just as in graphs, if a hypergraph is k-partite it is k-colorable. Often, studies of k-partite hypergraphs are restricted to k-uniform ones, where every edge has exactly one vertex from each of the k partitions.

Hypergraphica

To aide in the exploration of these objects, I'm developing a Mathematica package designed to extend the Combinatorica package to hypergraphs.

Ryser's Conjecture

The concepts of a graph's minimal covering $τ$ and maximal matching $ν$ can be extended to hypergraphs, as well. We notice that, for any type of graph - simple, directed, multi, hyper, ..., $\nu \leq \tau$ .

Konig proved that for bipartite graphs, also $\tau \leq \nu$ , and so in this case $τ = ν$ . Extending this concept to k-partite hypergraphs, Ryser conjectured that $\nu \leq (k-1) \tau$ - not quite as pretty in that it does not lead to equality, but still quite difficult: so far, it has only been proven for $k = 3$ .

Graph Interpretations of Hypergraphs

Line Graph

Inspired by Cvetkovic (http://www.emis.de/journals/BSANU/30/r2005_7.pdf)'s urging that some of a line graph's algebraic properties are more informative than those of the graph itself and the fact that the line graph of a hypergraph is just a graph, we hope to generalize some of the nice properties of the line graph to hypergraphs. From there, perhaps we can find some truths about certain families of hypergraph.

Total Graph

More complex and perhaps a little reduldant, the total graph (http://mathworld.wolfram.com/TotalGraph.html) of a graph consists of the disjoint union of a graph G with its line graph L(G), further edges added according to incidence of vertices in G and the corresponding edges' vertex representation in L(G). For n=|V| and m=|E|, the total graph's adjacency matrix is an (n+m)x(n+m) block matrix of the following form:

G |  I(G)
--+--------
 T|
I |  L(G)
  |

where I is the nxm incidence matrix of the graph and $I T$ its transpose.

We say this is redundant, because each piece of adjacency/incidence information is presented in (at least) two different ways - adjcaent vertices are connected both to each other and to the line graph representative of the edge which connectes them; likewise, adjacent lines' vertex representations are connected in the line graph and to the vertex in G at which they are coincident, as well as the actual lines themselves being adjacent in G.

The desire for a slimmer representation is also motivated by the fact that, unlike the line graph, the total matrix can not generalize as nicely to line graphs, as while there is a clean correspondance between graphs and their adjacency matrices, a great deal of information is lost in the transition between hypergraph and adjacency matrix. While with hypergraphs the adjacency matrix is iffy and it, along with the adjacency matrix of the line graph, both add some redundancies, the incidence matrix of a hypergraph retains all necessary information - so why not get rid of all the rest? This motivates the following:

Incidence Graph/Subdivisions

We define the incidence graph of a graph to be the graph represented by the following adjacency matrix:

0 |  I(G)
--+--------
 T|
I |   0
  |

which is nicer than the total graph in that it generalizes in graph form to hypergraphs (while the total graph of a hypergraph is still a hypergraph).

We notice that, in the case of graphs, the incidence graph is the complete subdivision (http://en.wikipedia.org/wiki/Graph_subdivision#Subdivisions) of G.

Guedes&Markenzon(2005) (http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000300005) cite Johnson&Pollak(1987) (http://www3.interscience.wiley.com/journal/113388370/abstract) as having used a similar structure for studying Zykov planarity of hypergraphs.

Here are some observations about incidence graphs!

Families of Hypergraphs

Complete Hypergraphs

In a complete hypergraph, the edge set consists of the power set of the vertices (it is debatable whether the empty set is allowable as an 'edge' in the hypergraph).

A complete k-uniform hypergraph has edge set $\begin{pmatrix} V \\ k \end{pmatrix}$ .

We can also consider complete k-partite hypergraphs, where with partitions there are no connections but between collections of partitions every possible edge exists.

Steiner Triple Systems

A particular type of 3-uniform hypergraph, a Steiner Triple System has the further restriction that any two vertices are included in a unique edge - equivalently, that for any two vertices there is a unique third.

As hypergraphs and incidence geometries are equivalent, any family of the later can be similarly explored in the light of the hypergraph.

Finite (and Infinite?) Topologies

A set system S on set $Ω$ is a topology if:

S contains the empty set and $Ω$
S is closed under union
S is closed under finite intersection.

Simplicial Complexes

A set system is considered a simplicial complex if every subset of included sets are also included.

Note that the only Simplicial Complex Topology is the Complete Hypergraph - the Power Set $P (Ω)$ .

Summing it up

Expanding the work of others on graphs to results on hypergraphs:

A corollary in Cvetkovic (http://www.emis.de/journals/BSANU/30/r2005_7.pdf)

In any graph the multiplicity of eigenvalue 0 of the signless Laplacian is equal to the number of bipartite components. (http://www.emis.de/journals/BSANU/30/r2005_7.pdf)

As the incidence graph $G I$ is entirely bipartite, the signless Laplacian of a hypergraph's incidence graph('s adjacency matrix) tells the number of bipartite components of $G I$ - the number of components of G.

Lemma: The incidence graph has the same number of connected components as the original hypergraph.

Pf: (Note: here, we use $\perp$ to stand for incidence of a vertex and an edge, $| |$ to represent nonincidence. We also use point-vertex and line-vertex, to distinguish in the incidence graph between those vertices representing points in the original graph and those representing lines.)

Both directions of this proof rely on the fact that $x \sim y$ in G iff $x \perp y$ in $G I$ .

If vertices a and b are in the same connected component of hypergraph G, then there exists a path $P (a, b) = (a, e 1, v 2, e 2,..., e k - 1, v k, e k, b)$ of consecutively incident vertices and edges of G connecting them. As $a \perp e_1 \perp v_2 \perp ... \perp v_k \perp e_k \perp b$ in G, $a^I \sim e_1^I \sim v_2^I \sim ... \sim v_k^I \sim e_k^I \sim b^I$ in $G I$ . As this holds for arbitrary a, b in the same component, any two connected points in G are connected in $G I$ , and so connected components in G are connected in $G I$ .

If conversely, point-vertices $a I, b I$ are in the same component of $G I$ , there exists a path $P(a^I, b^I)=(a^I, e_1^I, v_2^I, ..., v_k^I, e_k^I, b^I)$ of consecutively adjacent point-vertices and line-vertices connecting $a I, b I$ ; we know this path is alternating between point- and line-vertices as the incidence graph is bipartite. As $a^I \sim e_1^I \sim v_2^I \sim ... \sim v_k^I \sim e_k^I \sim b^I$ in $G I$ , $a \perp e_1 \perp v_2 \perp ... \perp v_k \perp e_k \perp b$ in G, and so there is a path $P (a, b) = (a, e 1, v 2,..., v k, e k, b)$ connecting a to b in G. As this holds for arbitrary $a I, b I$ in $G I$ , any two connected point-vertices in $G I$ are connected in G, and so connected components in $G I$ are connected in G.

Then there is a correspondance between the connected components of G and those of $G I$ , and the act of taking the incidence graph preserves the number of connected components ■

Therefore, the multiplicity of eigenvalue 0 in the signless Laplacian of a hypergraph's incidence graph is the number of connected components of the graph. Note that a graph is just a 2-uniform hypergraph, so we can use this method to calculate the number of connected components of a graph - then reapply the theorem to the graph itself to find how many of those are or are not bipartite.

Mohar (http://www.fmf.uni-lj.si/~mohar/Papers/Spec.pdf) mentions a corollary in Fiedler (http://dml.cz/bitstream/handle/10338.dmlcz/101168/CzechMathJ_23-1973-2_11.pdf)

If $G 1$ is a spanning subgraph of $G 2$ , then the second-smallest eigenvalues of the Laplacian $\lambda _2(G_1) \leq \lambda _2(G_2)$ . (http://www.fmf.uni-lj.si/~mohar/Papers/Spec.pdf) (origin) (http://dml.cz/bitstream/handle/10338.dmlcz/101168/CzechMathJ_23-1973-2_11.pdf)

Hypergraphs related by vertex addition/deletion have line graphs with the above spectral property.

Lemma: The hypergraph $G 1$ 's line graph $L G (G 1)$ is a subgraph of $L G (G 2)$ if $G 2$ is formed by vertex additions of $G 1$ (equivalently, if $G 1$ is formed by vertex deletions to $G 2$ ). This line graph spans the original so long as edges are neither created nor destroyed.

Pf: Given the first sentence, the second follows from the simple fact that a subgraph spans if it includes all the vertices of the original - as $LG(G_1) \subseteq LG(G_2)$ and $| L G (G 1) | = | E (G 1) | = | E (G 2) | = | L G (G 2) |$ , the subgraph spans.

Now, given a graph $G$ with m edges, its line graph $L G (G)$ has m vertices - no vertex addition nor deletion on $G 1$ will affect this. Furthermore, incidence in the line graph is determined by nonempty intersection in the graph: then the addition of vertices can only increase the number of edges in the line graph, nonempty intersection unattainable by additional shared points; similarly, deletion of vertices can only decrease the number of edges in the line graph, novel (non-nonempty) intersection unattainable by further vertex lack ■

Note that LG remains unchanged under deletion of vertices of G so long as the deleted set does not include the entire intersection of any two edges; similarly, LG is unchanged under addition so long as added edges appear only in either just one edge or intersections of edges which already include other vertices.

Then, as their line graphs are in a spanning subset relation, a hypergraph's line graph's second-smallest eigenvalue of the Laplacian is less than or equal to the second eigenvalue of any line graph of a hypergraph formed by vertex addition to the original hypergraph, and greater than or equal to the second eigenvalue of any line graph of a hypergraph formed by vertex deletion on the original.

Think about how this relates to the Interlacing Theorem (http://en.wikipedia.org/wiki/Min-max_theorem#Cauchy_interlacing_theorem).

Talk

We are going to MathFest2008 in Madison, WI!

Our presentations are Thursday, July 31st - I will be talking about motivating the study of graphical interpretations of hypergraphs.

... and after

Projective Plane

Incidence Graph

As the incidence duality of which we speak is equivalent in ideation to the duality of projective planes (under which Galois planes are self-dual), it makes a lot of sense to look at the incidence graph of projective planes.

We know (nondegenerate) projective planes' incidence graphs have girth 6 and diameter 3, and that any girth-6 diameter-3 bipartite graph is a projective plane's incidence graph... can we phrase the axioms for projective planes in terms of the incidence graph? This may allow one to quickly form girth-6 diameter-3 bipartite graphs.

First, as we do not wish to deal with multihypergraphs, we have the following restriction on the incidence graph:

No two points have the same set of neighbors.

(note that this may not be strictly necessary given the uniqueness condition below, but I still have to check that that's the case)

The adjacency and intersection criteria for projective planes dissolve into one clean rule for the incidence graph:

Any two points in the same partition have a unique common neighbor.

For nondegenerate projective planes, there is also the quadrilateral condition - there exist four points, no three of which are colinear. This is interpretable in the incidence graph, as well:

There is a set of four points in one partition, no three of which share the same neighbor.

(or equivalently, there is a set of 7 points, no 3 of which share a common neighbor)

Line Graph

By the intersection criterion, the line graph of a projective plane is a complete graph on n vertices. However, any hypergraph in which all edges intersect has complete line graph - this criterion is necessary but not sufficient for a projective plane.

Steiner System

Incidence Graph

The incidence graphs of Steiner Triple Systems on n points are $\left ( 3, \frac{n-1}{2} \right )$ -semiregular, as one can show the hypergraphs themselves to be 3-uniform and $\frac{n-1}{2}$ -regular, and each pair of line-vetices has at most one common neighbor, while each pair of point-vertices has exactly one, adjacent to one more point.

The Steiner systems (http://en.wikipedia.org/wiki/Steiner_system) of the form S(m-1, m, n)have $\left ( m, \frac{n-1}{m-1} \right )$ -semiregular incidence graph... I imagine there's a recurrance relation which can prove the semiregularity of any Steiner System's incidence graph and calculate r, s.

Line Graph

An n-vertex Steiner Triple System's line graph can be shown to be $3 \left ( \frac{n-3}{2} \right )$ -regular, while that of an S(m-1, m, n) Steiner system is $m \left ( \frac{n-m}{m-1} \right )$ -regular. It seems there should also be a recursive formula for the general line graph's regularity degree.

Topology

Can we phrase the axioms for a topology in terms of the incidence graph? The line graph?

Simplicial Complex

A simplicial complex's incidence graph will be a subgraph of its line graph.

Retrieved from "http://wiki.canisiusmath.net/index.php?title=Hypergraphs"

Views

Personal tools

Create an account or log in

Navigation

Search

Toolbox