PlanetMath: incidence structure

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

incidence structure

(Topic)

Let ${\cal P}$ and ${\cal B}$ be two disjoint sets; the elements of ${\cal P}$ will be termed points and those of ${\cal B}$ blocks. Now (throughout this article, a bullet point defines the term in boldface)

an incidence structure is a subset ${\cal I}\subseteq{\cal P}\times{\cal B}$

and a point $\hbox{\sc p}$ and a block $\hbox{\sc b}$ are said to be incident iff $(\hbox{\sc p},\hbox{\sc b})\in{\cal I}$ . The dual incidence structure ${\cal I}^*$ is the same structure with the labels “point” and “block” reversed.

Every block $\hbox{\sc b}$ has a set ${\cal P}_{\SS\rm B}\subseteq {\cal P}$ of points it is incident with. If ${\cal P}_{{\SS\rm B}'}\ne{\cal P}_{{\SS\rm B}''}$ whenever $\hbox{\sc b}' \ne \hbox{\sc b}''$ , the incidence structure is said to be simple. Now we could identify each block $\hbox{\sc b}$ with its ${\cal P}_{\SS\rm B}$ so that blocks no longer have sets of points they are incident with but are such sets. If we define it that way, then

$\circ$: a simple incidence structure consists of a set ${\cal P}$ and a set ${\cal B}\subseteq \mathop{\rm Pow}\nolimits {\cal P}$ where $\mathop{\rm Pow}\nolimits {\cal P}$ is the powerset of ${\cal P}$ (the set of subsets of ${\cal P}$ ).

A simple incidence structure is also called a hypergraph (with points as vertices, and blocks as an extended type of “edges” that are no longer restricted to exactly two vertices each).

Every point $\hbox{\sc p}$ also has a set ${\cal B}_{\SS\rm P}\subseteq {\cal B}$ of blocks it is incident with. Often, a simple incidence structure also has a simple dual, but the set theory formalism does not allow us to regard blocks as sets of points and simultaneously points as sets of blocks! Nevertheless, it is often useful to alternate between these dual interpretations.

Designs

A $\tau$ - $(\nu,\kappa,\lambda)$ design, aka $\tau$ -design or block design, is an incidence structure with
- $\vert{\cal P}\vert = \nu$ points in all,
- $\vert{\cal P}_{\SS\rm B}\vert = \kappa$ points in each block $\hbox{\sc b}$ , and such that
- any set $\hbox{\sc t}\subseteq {\cal P}$ of $\vert\hbox{\sc t}\vert=\tau$ points occurs as subset $\hbox{\sc t}\subseteq {\cal P}_{\SS\rm B}$ in exactly $\lambda$ blocks.

The parameters are often called , , , $\lambda$ (in mixed Latin and Greek alphabets). Note there may be several non-isomorphic designs with the same values of the parameters, and no designs at all for certain combinations of values.

Designs need not be simple (they can have repeated blocks), but they usually are (and don't) in which case $\hbox{\sc b}$ can again be used as synonym for ${\cal P}_{\SS\rm B}$ .

$\circ$: 0-designs ( $\tau=0$ ) are allowed.
$\circ$: 1-designs ( $\tau=1$ ) are known as tactical configurations.
$\circ$: 2-designs are called balanced incomplete block designs or BIBD.
$\circ$: 3, 4, 5... -designs have all been studied.

Being a $\tau$ - $(\nu,\kappa,\lambda)$ design implies also being an $\iota$ - $(\nu,\kappa,\lambda_{\,\iota})$ design for every $0\le\iota\le\tau$ (on the same $\nu$ points and with the same block size $\kappa$ ), with $\lambda_{\,\iota}$ given by $\lambda_{\,\tau}=\lambda$ and recursively

$\begin{displaymath} \lambda_{\,\iota} \,=\; {\nu-\iota \over \kappa-\iota} \,\lambda_{\,\iota+1} \end{displaymath}$

from which we get the number of blocks as

$\begin{displaymath} \lambda_0 \,=\; {\nu!\,/\,(\nu-\tau)! \over \kappa!\,/\,(\kappa-\tau)!} \;=\; {\nu\choose\tau} \bigg/ {\kappa\choose\tau} \end{displaymath}$

Being a 0-design says nothing more than all blocks having the same size. As soon as we have $\tau\ge1$ however we also have a 1-design, so the number $\lambda_1 = \vert{\cal B}_{\SS\rm P}\vert$ of blocks per point is constant throughout the structure. Note now

$\begin{displaymath} \lambda_0\,\kappa \;=\; \lambda_1\,\nu \end{displaymath}$

which is also evident from their interpretation.

As an example: designs (simple designs) with $\kappa=2$ are multigraphs (simple graphs), now

$\circ$: $\tau=0$ implies no more than that,
$\circ$: $\tau=1$ gives regular graphs, and
$\circ$: $\tau=2$ gives complete graphs.

A more elaborate “lambda calculus” (pun intended) can be introduced as follows. Let ${\rm I}\subseteq{\cal P}$ and ${\rm O}\subseteq{\cal P}$ with $\vert{\rm I}\vert=\iota$ and $\vert{\rm O}\vert=o$ . The number of blocks $\hbox{\sc b}$ such that all the points of ${\rm I}$ are inside $\hbox{\sc b}$ and all the points of ${\rm O}$ are outside $\hbox{\sc b}$ is independent of the choice of ${\rm I}$ and ${\rm O}$ , only depending on $\iota$ and , provided $\iota+o\le\tau$ . Call this number $\lambda_\iota^o$ . It satisfies a kind of reverse Pascal triangle like recursion

$\begin{displaymath} \lambda_\iota^o\,=\, \lambda_{\iota+1}^o+ \lambda_\iota^{o+1} \end{displaymath}$

that starts off for

with $\lambda_\iota^0 = \lambda_\iota$ . An important quantity (for designs with $\tau\ge2$ ) is the order $\lambda_1^1 = \lambda_1^0 - \lambda_2^0 = \lambda_1 - \lambda_2$ .

Finally, the dual of a design can be a design but need not be.

A square design aka symmetric design is one where $\tau=2$ and $\vert{\cal P}\vert=\vert{\cal B}\vert$ , now also $\vert{\cal P}_{\SS\rm B}\vert=\vert{\cal B}_{\SS\rm P}\vert$ . Here the dual is also a square design.

Note that for $\tau\ge3$ no designs exist with $\vert{\cal P}\vert=\vert{\cal B}\vert$ other than trivial ones (where any $\kappa=\nu-1$ points form a block).

Steiner systems

An $S(\tau,\kappa,\nu)$ Steiner system is a $\tau$ - $(\nu,\kappa,1)$ design (i.e. $\lambda=1$ ).

Again, there may be several non-isomorphic systems with the same values of the parameters, and no systems at all for certain combinations of values. Note that $\lambda=1$ implies a simple incidence structure; from now on we will interpret a block to be a set of points ( $\hbox{\sc b}={\cal P}_{\SS\rm B}$ ).

Let ${\cal S}$ be an $S(\tau,\kappa,\nu)$ with point set ${\cal P}$ and block set ${\cal B}$ , and choose a point $\hbox{\sc p}_0\in {\cal P}$ (often, the system is so symmetric that it makes no difference which point you choose). The choice uniquely induces an $S({\tau-1},\,\allowbreak {\kappa-1},\,\allowbreak {\nu-1})$ ${\cal S}_1$ with point set ${\cal P}_1 = {\cal P}\setminus\{\hbox{\sc p}_0\}$ and block set ${\cal B}_1$ consisting of $\hbox{\sc b}\setminus\{\hbox{\sc p}_0\}$ for only those $\hbox{\sc b}\in{\cal B}$ that contained $\hbox{\sc p}_0$ . This works because for any $\hbox{\sc t}_1\subseteq{\cal P}_1$ with $\vert\hbox{\sc t}_1\vert=\tau-1$ there was a unique $\hbox{\sc b}\in{\cal B}$ that contained $\hbox{\sc t}=\hbox{\sc t}_1\cup\{\hbox{\sc p}_0\}$ .

This recurses down all the way to $\tau=1$ (a partition of $\nu-\tau+1$ into blocks of $\kappa-\tau+1$ ) and finally to $\tau=0$ (one arbitrary block of $\kappa-\tau$ ). If any of the divisibility conditions on the way there do not hold, there cannot exist a Steiner system with the original parameters either.

For instance, Steiner triple systems $S(2,3,\nu)$ (the first Steiner systems studied, by Kirkman, before Steiner) exist for $\nu=0$ and all $\nu\equiv1$ or $3\allowbreak \mkern 10mu({\rm mod}\,\,6)$ , and no other $\nu$ .

The reverse construction, turning an $S(\tau,\kappa,\nu)$ into an $S({\tau+1},\,\allowbreak {\kappa+1},\,\allowbreak {\nu+1})$ , need not be unique and may be impossible. Famously an and a have the Mathieu groups $M_{11}$ and $M_{12}$ as their automorphism groups, while $M_{22}$ , $M_{23}$ and $M_{24}$ are those of an , and , with connexions to the binary Golay code and the Leech lattice.

Finite planes

The term line has a specific meaning for 2-designs in general: for any two points, it is the intersection of all blocks containing both those points. For 2-designs that are also Steiner systems ( $\tau=2$ and $\lambda=1$ ) there is only one such block, so line becomes a synonym for block. And it becomes a finite analogue of the usual geometric meaning of the word.

An $S(2,\kappa,\nu)$ is the finite analogue of a plane, with blocks in the rôle of lines

in the following sense: the design property now requires there to be, for any two different points, exactly one line “through” both those points. Just like in a real (continuous) plane.

This also implies that, for any two different lines and , there is no more than one point “on” both those lines (if both of $\hbox{\sc p}$ and $\hbox{\sc q}$ were on both those lines, there would be two lines through those points). It does not imply there is always such a point: just like in a real plane, lines can be parallel.

One example is a (finite) affine plane with points and lines. It can be obtained by deleting one line (and all its points) from a projective plane (for which see below). Lines that used to intersect in one of the deleted points are parallel in the affine plane.

A (finite) projective plane is an $S(2,\,\allowbreak q+1,\,\allowbreak q^2+q+1)$

and it has no parallel lines. Because any two lines meet in a point, the dual is again a projective plane. So a projective plane is a square design, as well as being a great many other things.

It is easy to prove that the property of being a plane dual to a plane (i.e. the absence of parallel lines) implies, apart from a few trivial cases, numbers of the form and . Much harder is determining for which such planes exist. The parameter is known as the order of the plane (this agrees with order as defined above for designs in general).

Highly symmetric “classical” (aka Desarguesian, Pappian) projective planes can be constructed based on finite fields, for any prime power . Many non-Desarguesian projective planes are known, but thus far their are also prime powers. The prime power conjecture is that orders of all projective planes will be prime powers.

The Bruck-Ryser theorem states that if $q\equiv1$ or $2\allowbreak \mkern 10mu({\rm mod}\,\,4)$ , and not (a square or) the sum of two squares, it cannot be the order of a projective plane. This rules out 6 for instance, as well as 14 etc. It has been extended to the Bruck-Ryser-Chowla theorem for all square 2-designs, with a more complicated constraint.

The only other order ruled out to date is 10, via an epic computer search by Lam, Swiercz and Thiel (read http://www.cecm.sfu.ca/organics/papers/lam/index.html for Lam's account).

Bibliography

AK93: E.F.ASSMUS and J.D.KEY, Designs and their Codes
(pbk. ed. w. corr.), Camb. Univ. Pr. 1993, ISBN0521458390
first part has thorough introduction to various flavors of incidence structure
Cam94: PETER J.CAMERON, Combinatorics: topics, techniques, algorithms,
Camb. Univ. Pr. 1994, ISBN0521457610
http://www.maths.qmul.ac.uk/˜pjc/comb/ (solutions, errata &c.)
good combinatorics textbook, with detail
Pot95: ALEXANDER POTT, Finite Geometry and Character Theory,
Lect. Notes in Math. 1601, Springer 1995, ISBN354059065X
includes clear introduction to incidence structures
CD96: CHARLES J.COLBOURN and JEFFREY H.DINITZ, eds.
The CRC Handbook of Combinatorial Designs,
CRC Press 1996, ISBN0849389488
http://www.emba.uvm.edu/˜dinitz/hcd.html (errata, new results)
the reference work on designs incl. Steiner systems, proj. planes

"incidence structure" is owned by marijke.

(view preamble)

Also defines:

design, block, block design, $\tau$ -design, simple design, square design, symmetric design, tactical configuration, balanced incomplete block design, BIBD, Steiner system, Steiner triple system, projective plane, finite projective plane, affine plane, finite affine plane

Keywords:

incidence, block, design

Log in to rate this entry.
(view current ratings)

Cross-references: epic, sum of two squares, prime power conjecture, power, prime, finite fields, parallel lines, parallel, continuous, real, plane, finite, intersection, line, lattice, binary Golay code, automorphism groups, groups, divisibility, partition, contained, induces, symmetric, Pascal triangle, independent, complete graphs, regular graphs, graphs, multigraphs, number, implies, Greek alphabets, parameters, interpretations, set theory, vertices, hypergraph, powerset, labels, iff, subset, points, disjoint
There are 45 references to this entry.

This is version 4 of incidence structure, born on 2005-04-08, modified 2005-04-09.
Object id is 6937, canonical name is IncidenceStructures.
Accessed 13148 times total.

Classification:

AMS MSC:	05B05 (Combinatorics :: Designs and configurations :: Block designs)
	05B07 (Combinatorics :: Designs and configurations :: Triple systems)
	05B25 (Combinatorics :: Designs and configurations :: Finite geometries)
	51E05 (Geometry :: Finite geometry and special incidence structures :: General block designs)
	51E30 (Geometry :: Finite geometry and special incidence structures :: Other finite incidence structures)
	62K10 (Statistics :: Design of experiments :: Block designs)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

Interact

post | correct | update request | add example | add (any)