|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: Hypergraphs''
by marijke on 2005-03-30 22:04:01 |
|
| 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/ |
| | [ reply | up | top ] | |
|
|
|
|
|
|
|
