# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Incidence structure

 Contents

## Definition

In mathematics, in particular in combinatorics, an incidence structure is a triple

C = (P,L,I)

where P is the set of "points", L is the set of "lines" and $I \subseteq P \times L$ is the incidence relation. The elements of I are called flags. If $(p,l) \in L$ we say that "point" p lies on "line" l.

## Dual structure

If we interchange the role of "points" and "lines" in

C = (P,L,I)

the dual structure

C * = (L,P,I * )

is obtained. Clearly

C * * = C.

A structure C that is isomorphic to its dual C * is called self-dual.

## Hypergraphs as incidence structures

Each hypergraph or set system can be regarded as an incidence structure in which the universal set plays the role of "points", the corresponding family of sets plays the role of "lines" and the incidence relation is given by $\in$.

## Example: Fano plane

In particular, let

P = {1,2,3,4,5,6,7},
L = {{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}
$I = \in$.

The corresponding incidence structure is called the Fano plane.

## Geometric representation

Incidence structures can be modelled by points and curves in the Euclidean plane whith usual geometric incidence. Some incidence structures admit representation by points and lines. Fano plane is not one of them since it needs atr least one curve.

## Incidence structure and its Levi graph

To each incidence structure C we may associate a bipartite graph called Levi graph or incidence graph with a given black and white vertex coloring where black vertices correspond to points and white vertices correspond to lines of C and the edges correspond to flags.

## Example (revisited)

For instance, the Levi graph of the Fano plane is the Heawood graph. Since the Heawood graph is connected and vertex-transitive, it follows that there exists an automorphism (such as the one defined by a reflection about the vertical axis in the above figure) interchanging black and white vertices. This, in turn, implies that the Fano plane is self-dual.