Math for the people, by the people.

User login

hypergraph

Defines: 
incidence matrix, uniform hypergraph, regular hypergraph
Keywords: 
finite and infinite hypergraphs, edge sets, vertices, matrix representations of hypergraphs
Synonym: 
metacategory, multi-graph, colored graph
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

05C65 no label found

Comments

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?

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/

> 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

> 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/

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.

Subscribe to Comments for "hypergraph"