hypergraph
Primary tabs
hypergraph
A hypergraph is an ordered pair where is a set of vertices and is a set of edges such that . In other words, an edge is nothing more than a set of vertices. A hypergraph is the same thing as a simple incidence structure, but with terminology that focuses on the relationship with graphs.
Sometimes it is desirable to restrict this definition more. The empty hypergraph is not very interesting, so we usually accept that . Singleton edges are allowed in general, but not the empty one. Most applications consider only finite hypergraphs, but occasionally it is also useful to allow to be infinite.
Many of the definitions of graphs carry verbatim to hypergraphs.
is said to be -uniform if every edge has cardinality , and is uniform if it is -uniform for some . An ordinary graph is merely a uniform hypergraph.
The degree of a vertex is the number of edges in that contain this vertex, often denoted . is -regular if every vertex has degree , and is said to be regular if it is -regular for some .
Let and . Associated to any hypergraph is the incidence matrix where
For example, let , where and . Defining and in the obvious manner (as they are listed in the sets), we have
Notice that the sum of the entries in any column is the cardinality of the corresponding edge. Similarly, the sum of the entries in a particular row is the degree of the corresponding vertex.
The transpose of the incidence matrix also defines a hypergraph , the dual of , in an obvious manner. To be explicit, let where is an -element set and is an -element set of subsets of . For and if and only if .
Continuing from the example above, the dual of consists of and , where and are defined in the obvious manner.
By the remark immediately after the definition of the incidence matrix of a hypergraph, it is easy to see that the dual of a uniform hypergraph is regular and vice-versa. It is not rare to see fruitful results emerge by considering the dual of a hypergraph.
Note A finite hypergraph is also related to a metacategory, and can be shown to be a special case of a supercategory, and can be thus defined as a mathematical interpretation of ETAS axioms.
Mathematics Subject Classification
05C65 Hypergraphs
Comments
Hypergraphs
At last - found it!
I hit on the idea of a hypergraph (from the perspective of generalising geometry, not from graph theory) a few months ago, and have been earnestly looking for any mention of what I called 'generalised polygons' (only I realised somebody else had got there first with that term).
Only today did I think of the perspective of graph theory, and found this article defining hypergraph.
Coming as I did from a geometric standpoint, I have been exploring things like the order and symmetries of the simplest non-trivial k-uniform hypergraphs. Does anybody know any work on this topic?
Re: Hypergraphs
Hi drini, and colin,
just reading the hypergraph article. I've come across the term "incidence structure" in the literature, and it appears to be pretty much the same thing! Would you (drini) consider mentioning it as a synonym? The terminology i know is
- incidence structure: anything goes (BTW, the sets of two kinds
of things are often called "points" and "blocks") -- the incidence
structure ${\cal I}$ is then defined as a subset of
${\cal P} \times {\cal B}$ where the latter are the set of points
and set of blocks respectively. But also as a matrix as you do.
- *simple* inc. str. means each block (edge) has a unique set of
points (vertices) it is incident with. In this case you could
say a block *is* rather than *has* a set of points, because no
two blocks are the same element of Powerset(P). Maybe you already
implied that.
- there doesn't seem to be a word for being simple both ways (i.e.
the dual also being simple)
- $\mu$-($\nu,\kappa,\lambda$)-design or $t$-($v,k,\lambda$)-design
(where $\nu$ is the total number of points): now the thing is what
you call uniform (each block has $\kappa$ points) but there's also
a good deal more going on: each subset of $\mu$ points occurs in
exactly $\lambda$ of the blocks. Recursively you can show each
subset of $\kappa-1$, $\kappa-2$ ... occur in so and so many
blocks (basically by considering only the blocks through one
particular point), the numbers go a bit like binomial coeffs.
as in, factorials fivided by factorials divided by...
Dual of a design need not be a design (there doesn't seem to be
a name for being a design both ways).
- square design, symmetric design: number of points = number of
blocks. Dual of this one is an s. des. as well.
- Steiner system: design with $\lambda = 1$. Notation
$S(\mu,\kappa,\nu)$ :: $\mu$-($\nu,\kappa,1$)-design
- Steiner triple system: $\lambda = 1$, $\mu = 2$, $\kappa = 3$
- Projective plane: Steiner system $(2, q+1, q^2+1)$ ::
2-($q^2+1, q+1, 1$)-design.
> Coming as I did from a geometric standpoint, I have been exploring
> things like the order and symmetries of the simplest non-trivial
> k-uniform hypergraphs. Does anybody know any work on this topic?
\bitem{AK93} \name{Ed\,F.\,Assmus} \& \name{Jenny\,D.\,Key},
\book{Designs and their Codes}
(pbk.~ed.~w.~corr.), Camb.~Univ.~Pr.~1993,
\isbn{0\,521\,45839\,0}
\bitem{Pot95} \name{Alexander Pott},
\book{Finite Geometry and Character Theory},
Lect.~Notes~in~Math.~\vol{1601}, Springer~1995,
\isbn{3\,540\,59065\,X}
\bitem{CD96} \name{Charles J.\,Colbourn} \&
\name{Jeffrey H.\,Dinitz}, eds.\
\book{The CRC Handbook of Combinatorial Designs},
CRC~Press~1996, \isbn{0\,8493\,8948\,8}\\
\url{http://www.emba.uvm.edu/~dinitz/hcd.html}
(errata, new results)
are some places to look. Enjoy...
--regards, marijke
http://web.mat.bham.ac.uk/marijke/
Re: Hypergraphs
> just reading the hypergraph article. I've come across the
> term "incidence structure" in the literature, and it appears
> to be pretty much the same thing! Would you (drini) consider
> mentioning it as a synonym? The terminology i know is
even better, go ahead and make the changes your self so you can improve it the best way you see fit
f
G -----> H G
p \ /_ ----- ~ f(G)
\ / f ker f
G/ker f
Re: Hypergraphs
> even better, go ahead and make the changes your self so you can
> improve it the best way you see fit
Thanks but... i didn't think the article was bad, just that it was worth mentioning these critters also go by the name "incidence structures". In case somebody looks for them by that name.
At the moment i'm till over my ears in
* making those pictures for $k$-connected graphs (my first article
here, an adopted orphan) that were requested, of the previous
custodian, about a year ago -- just finished the pix offline, now
going to find out how to put them in here. Perhaps the kind of
topic that hangs off a parent topic (whatever that setup is called
again) would be a good idea. On the case.
* cleaning up [closed] paths, trails, walks etc., my second article
-- just done that
* writing the Coxeter groups article -- i find it is getting far
too long for an encyclop{\ae}dia entry, is there another format
for more in-depth articles?
So no i'm not exactly jumping at the chance right now to edit Hypergraphs ;^)
It's a good job i'm having 4 weeks holiday between terms at the moment... --- and 'flu :( lousy for going outside and doing things, but it doesn't seem to affect writing and thinking much.
...i hope <ggg>.
--regards, marijke
http://web.mat.bham.ac.uk/marijke/
Is there this kind of graph?
The vertex of this kind of graph is hyper-vertex, i.e. the vertex might be a graph itself, while the edges are normal. In contrast, the hyper-graph has special edges, hyper-edges.