Lectures in Combinatorics

1. Partially Ordered Sets

Elementary Definitions.

A poset (partially ordered set) is a set P with a binary relation £ such that for all a, b, c Î P:

a £ a
if a £ b and b £ c then a £ c
if a £ b and b £ a then a = b

If a £ b and a ¹ b we write a < b. We say that b covers a if a £ b and there does not exist c such that a < c < b. A subset C of P is called a chain if for any a, b ÎC, either a £ b or b £ a. A subset A of P is called an antichain if for any two distinct a, b Î A, neither a £ b nor b £ a.

Examples.

P = Z, the set of integers, ordered by the usual order £.
P is a set of divisors of a given natural number n, ordered by divisibility |.
P is a set of subsets of a given set S, ordered by set inclusion Í.

It is often convenient to draw a poset diagram with dots representing the elements of P and a decending line connecting b with a whenever b covers a.

**Fig 1.** (a) Poset of integers, (b) poset of divisors of 12 and (c) poset of subsets of {1,2,3}

Dilworth's Theorem.

Consider the poset P of subsets of {1,2,3} ordered by set inclusion shown in fig 1(c). There is a decomposition of the poset into 3 disjoint chains P = C₁ È C₂È C₃ where:

C₁ = {{ },{1},{1,2},{1,2,3}}
C₂ = {{2},{2,3}}
C₃ = {{3},{1,3}}

There are other ways of decomposing P into disjoint chains, but a quick inspection shows that you cannot do it with less than 3 disjoint chains. On the other hand, there is an antichain in P with 3 elements, namely:

A = {{1},{2},{3}}

There are other antichains in P but a quick inspection shows that you cannot find an antichain with more than 3 elements. So the minimum number of chains that partition P is equal to the size of a maximal antichain in P.

**Fig 2.** Decomposition of the posets of fig 1 into a minimal number of chains (red, blue, green) and a maximal antichain (yellow). In each case the two numbers are equal.

Robert Dilworth [1] observed that this equality is true for finite posets in general.

Theorem 1. Let P be a finite poset. Let m be the minimum number of disjoint chains that together contain all elements of P. Let M be the maximum number of elements in an antichain of P. Then m = M.

Proof. This proof is due to Helge Tverberg [2]. We show that (i) m ³ M and (ii) m £ M. Observe that (i) follows from the fact that for any antichain with M elements we must have at least M disjoint chains, each containing one element of the antichain, in order to obtain a decomposition of P. For (ii) we use induction on |P|. If |P| = 0, the theorem is vacuously true. Assume that the theorem is true for all posets with less than |P| elements. Let C be a maximal chain in P. If every antichain in P \ C has at most M - 1 elements, we are done. So suppose {a₁, ..., a_M} is an antichain in P \ C. Define

Q = { x Î P : x £ a_i for some i}
R = { x Î P : x ³ a_i for some i}

Since C is a maximal chain, the largest element of C is not in Q. So |Q| < |P| and by the induction hypothesis, the theorem is true for the poset Q. Hence Q is the union of disjoint chains Q₁, ..., Q_M, where a_i Î Q_i. We claim that a_i is the maximal element of chainQ_i (Suppose a Î Q_i and a_i < a. Since a £ a_j for some j, we have a contradiction a_i < a_j). Similarly, R is the union of disjoint chains R₁, ..., R_M, where a_iÎ R_i, and we can show that a_i is the minimal element of chain R_i. The theorem follows by combining the respective chains along the elements of the antichain. ¨

2. Lattices

Elementary Definitions.

A lattice is a poset L with the property that any finite subset has a least upper bound (called join) and a greatest lower bound (called meet). For any pair of not necessarily distinct elements x and y, the join and meet are denoted by x Ú y and x Ù y respectively. The posets shown in fig 1 (a), (b), (c) are all lattices. The lattice shown in fig 1(a) is an example of a lattice with an infinite chain. We shall only be interested in lattices that have no infinite chains, for such lattices have a unique minimum element called 0 and a unique maximum element called 1. A point of such a lattice is an element that covers 0. A lattice is called atomic if each element is a join of points. A lattice is semimodular if whenever distinct a and b cover c then a Ú b covers both a and b. A geometric lattice is a lattice L with the following properties:

L has no infinite chains
L is atomic
L is semimodular

Exercise. Are the lattices shown in fig 1(a) and fig 1(b) geometric lattices? Show that the lattice shown in fig 1(c) is a geometric lattice.

Given a geometric lattice L, let X denote its set of points. For each y Î L, define F_y = { x Î X : x £ y }. Define the set F = { F_y : y Î L }. Then (X, F) is called a combinatorial geometry with the elements of X called points and the elements of F called flats.

Examples.

Consider the geometric lattice shown in fig 1(c). The set of points is X = {{1},{2},{3}}. The set of F of flats is given by

F_{} = {}
F_{1} = {{1}}
F_{2} = {{2}}
F_{3} = {{3}}
F_{1,2} = {{1},{2}}
F_{1,3} = {{1},{3}}
F_{2,3} = {{2},{3}}
F_{1,2,3} = {{1},{2},{3}}

Consider the geometric lattice shown in fig 3 below:

**Fig 3.** A geometric lattice consisting of certain subsets of {0,1,2,3,4,5,6} ordered by set inclusion.

The set of points is X = {{0},{1},{2},{3},{4},{5},{6}}. The set F of flats is given by

{}
{{0}}
{{1}}
{{2}}
{{3}}
{{4}}
{{5}}
{{6}}
{{1},{2},{4}}
{{0},{1},{3}}
{{0},{2},{6}}
{{0},{4},{5}}
{{3},{4},{6}}
{{1},{5},{6}}
{{2},{3},{5}}
{{0},{1},{2},{3},{4},{5},{6}}}

Exercise. Show that the poset of fig 3 is a geometric lattice.

3. Projective Planes

There is a very nice way of visualizing the combinatorial geometry of the last example, discovered by Gino Fano [3]. Represent the one-element flats by dots and the three-element flats by curves connecting the respective dots. We obtain the famous configuration known as the Fano Plane:

**Fig 4.** The Fano plane

A finite projective plane of order n is a set of n² + n + 1 points and a set of n² + n + 1 subsets of points called lines such that

Any two distinct points determine a unique line
Any two distinct lines determine a unique point
Every point is contained in exactly n + 1 lines
Every line contains exactly n + 1 points

The finite projective plane of order n = 2, the Fano plane, is shown above in fig 4. It is easy to show that

For every prime power q = p^k, there exists a projective plane of order q.

Consider the three-dimensional vector space GF(q) Å GF(q) Å GF(q) over the Galois field GF(q). This vector space contains (q³ - 1)/(q - 1) = q² + q + 1 one-dimensional subspaces (define these to be the points of the projective plane) and the same number of two-dimensional subspaces (define these to be the lines of the projective plane). A projective plane of order q constructed in this way is usually denoted by the symbol PG(2,q). Thus the Fano plane is PG(2,2).

Exercise. Show that the PG(2,q) construction satisfies the geometric definition of a projective plane of order q.

A long standing unsolved problem in combinatorics is the following:

Do there exist projective planes of order n, where n is not a prime power?

It was proved by R.H. Bruck and Herbert Ryser [4] that if n º 1 or 2 (mod 4), and a projective plane of order n exists, then n must be the sum of two squares. So, for example, there cannot exist a projective plane of order n = 6 because 6 º 2 (mod 4) and 6 is not the sum of two squares. However, what about values of n that are not prime powers and not º 1 or 2 (mod 4)? It is suspected that there are no projective planes of order n = 10, based on extensive computer searches. The case n = 12 is still open. The general problem still remains unsolved even for small values of n.

References.

[1] Robert P. Dilworth, A decomposition theorem for partially ordered sets, Annals of Math. (2) 51,161-166, 1950.

[2] Helge Tverberg, On Dilworth's decomposition theorem for partially ordered sets, J. Combinatorial Theory (3), 305-306, 1967.

[3] Gino Fano, Giornale di Matimatiche (30), 114-124, 1892.

[4] R.H. Bruck and Herbert J. Ryser, The nonexistence of certain finite projective planes, Canad. J. Math. 1, 88-93, 1949.

This website is hosted for free by

. Get your own Free Website now!