## You are here

Homehypergraph

## Primary tabs

# hypergraph

A *hypergraph* $\mathcal{H}$ is an ordered pair $(V,\mathcal{E})$ where $V$ is a set of *vertices* and $\mathcal{E}$ is a set of edges such that $\mathcal{E}\subseteq\mathcal{P}(V)$. 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 $V\not=\emptyset$. 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 $V$ to be infinite.

Many of the definitions of graphs carry verbatim to hypergraphs.

$\mathcal{H}$ is said to be $k$-*uniform* if every edge $e\in\mathcal{E}$ has cardinality $k$, and is *uniform* if it is $k$-uniform for some $k$. An ordinary graph is merely a $2-$uniform hypergraph.

The *degree* of a vertex $v$ is the number of edges in $\mathcal{E}$ that contain this vertex, often denoted $d(v)$. $\mathcal{H}$ is $k$-*regular* if every vertex has degree $k$, and is said to be *regular* if it is $k$-regular for some $k$.

Let $V=\{v_{1},v_{2},~{}\ldots,~{}v_{n}\}$ and $\mathcal{E}=\{e_{1},e_{2},~{}\ldots,~{}e_{m}\}$. Associated to any hypergraph is the $n\times m$ *incidence matrix* $A=(a_{{ij}})$ where

$a_{{ij}}=\begin{cases}1&\text{ if }~{}v_{i}\in e_{j}\\ 0&\text{ otherwise }\end{cases}$ |

For example, let $\mathcal{H}=(V,\mathcal{E})$, where $V=\{a,b,c\}$ and $\mathcal{E}=\{\{a\},\{a,b\},\{a,c\},\{a,b,c\}\}$. Defining $v_{i}$ and $e_{j}$ in the obvious manner (as they are listed in the sets), we have

$A=\begin{pmatrix}1&1&1&1\\ 0&1&0&1\\ 0&0&1&1\end{pmatrix}$

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 $A^{t}$ of the incidence matrix also defines a hypergraph $\mathcal{H}^{*}$, the *dual* of $\mathcal{H}$, in an obvious manner. To be explicit, let $\mathcal{H}^{*}=(V^{*},\mathcal{E}^{*})$ where $V^{*}$ is an $m$-element set and $\mathcal{E}^{*}$ is an $n$-element set of subsets of $V^{*}$. For $v^{*}_{j}\in V^{*}$ and $e^{*}_{i}\in\mathcal{E}^{*},~{}v^{*}_{j}\in e^{*}_{i}$ if and only if $a_{{ij}}=1$.

Continuing from the example above, the dual $\mathcal{H}^{*}$ of $\mathcal{H}$ consists of $V^{*}=\{x,y,z,t\}$ and $\mathcal{E}^{*}=\{\{x,y,z,t\},\{y,t\},\{z,t\}\}$, where $v^{*}_{j}$ and $e^{*}_{i}$ 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*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## 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.