🔢Enumerative Combinatorics Unit 11 – Combinatorial Designs & Finite Geometries

Key Concepts and Definitions

• Combinatorial designs involve arranging elements into subsets or blocks according to specific rules and constraints
• Balanced incomplete block designs (BIBDs) ensure each pair of elements occurs together in a fixed number of blocks
• Incidence structures consist of points and lines (or blocks) with an incidence relation between them
• Automorphisms are permutations of points and blocks that preserve the incidence structure
• Resolvability means the blocks can be partitioned into parallel classes, each forming a partition of the point set
• Steiner systems are BIBDs with parameters $(v,k,1)$, meaning each pair of points occurs in exactly one block
• $t$-designs extend the concept of BIBDs, requiring each $t$-subset of points to occur in a fixed number of blocks
  • Steiner triple systems (STS) are $2$-designs with block size $k=3$

Historical Context and Applications

• Combinatorial designs originated from recreational mathematics, such as Kirkman's schoolgirl problem (1850)
• R.C. Bose and R.A. Fisher independently developed the theory of BIBDs in the context of statistical design of experiments (1930s)
• Applications in coding theory involve constructing error-correcting codes from combinatorial designs
  • Hadamard matrices and difference sets are used to construct linear codes with good properties
• Designs are used in cryptography for key distribution schemes and authentication codes
• Tournament scheduling often employs balanced tournament designs to ensure fairness and balance
• Experimental design in agriculture, medicine, and social sciences relies on BIBDs for efficient and unbiased treatment comparisons
• Finite projective planes have connections to the theory of quasigroups and Latin squares in algebra

Types of Combinatorial Designs

• Symmetric designs have the same number of points as blocks and each block contains the same number of points as the number of blocks containing a given point
• Cyclic designs admit a cyclic automorphism group acting regularly on the points
• Resolvable designs can be partitioned into parallel classes, each containing disjoint blocks
• Affine designs are resolvable designs with additional regularity properties related to parallelism
• Pairwise balanced designs (PBDs) relax the condition of BIBDs, allowing for varying block sizes
• Orthogonal arrays are "designs" with strength $t$, where each $t$-tuple of points occurs equally often as a row in an array representation
• Latin squares are $n \times n$ arrays filled with $n$ symbols, each occurring once in each row and column
  • Mutually orthogonal Latin squares (MOLS) have the property that superimposing any two squares yields all ordered pairs of symbols

Finite Geometries: Basics and Structure

• Finite geometries have a finite number of points and lines satisfying certain incidence axioms
• Finite projective planes are the most well-studied finite geometries, characterized by the projective axioms:
  1. Any two points determine a unique line
  2. Any two lines intersect in a unique point
  3. There exist four points, no three of which are collinear
• The order $n$ of a projective plane is the number of points on each line minus one
  • Projective planes of prime power order $q$ can be constructed using finite fields $\mathbb{F}_q$
• Finite affine planes are obtained by removing a line and its points from a projective plane
• Generalized quadrangles, hexagons, and octagons are finite geometries with additional regularity conditions on the incidence structure
• Polar spaces and generalized polygons provide a unified framework for studying finite geometries

Construction Techniques

• Difference methods use difference sets or relative difference sets to construct designs with cyclic or group structure
  • Singer difference sets yield cyclic projective planes and symmetric designs
• Finite fields and vector spaces over them are used to construct affine and projective geometries
  • Oval and hyperoval constructions in projective planes of even order
• Orthogonal arrays can be constructed from linear codes, affine geometries, and transversal designs
• Recursive constructions build larger designs from smaller ones
  • Wilson's Fundamental Construction for BIBDs and PBDs
  • Product constructions for orthogonal arrays and Latin squares
• Algebraic methods involve group actions, character sums, and cyclotomy in finite fields
• Computer search and combinatorial optimization techniques are used for small parameter sets or when no theoretical construction is known

Counting and Enumeration Methods

• Incidence matrices and their eigenvalues are used to count and characterize designs
  • Wilson's inequality gives necessary conditions for the existence of BIBDs
• The Krein conditions use algebraic graph theory to constrain the parameters of symmetric designs
• Orbit-stabilizer theorem and Burnside's lemma count designs with prescribed automorphism groups
• The Erdős-Ko-Rado theorem bounds the size of a family of intersecting blocks in a design
• Linear programming methods optimize over the convex hull of incidence vectors of blocks
• Enumeration of small designs is done by computer search and classification up to isomorphism
  • Complete classifications are known for Steiner triple systems of order up to 19 and projective planes of order up to 9

Connections to Other Mathematical Fields

• Algebraic graph theory studies strongly regular graphs arising from symmetric designs and finite geometries
• Coding theory uses designs to construct error-correcting codes and to study their weight enumerators
• Matroid theory generalizes the concept of linear independence to finite geometries and designs
• Group theory, especially permutation groups and representation theory, is used to study automorphism groups and block transitivity of designs
• Number theory, particularly character sums and cyclotomy, is employed in algebraic constructions of designs
• Extremal combinatorics investigates the maximum size of a family of blocks with certain intersection properties
• Finite geometry has deep connections with algebraic geometry over finite fields and the theory of curves and surfaces

Advanced Topics and Open Problems

• The existence conjecture for projective planes states that they exist for all orders $n$ that are prime powers
  • The non-existence of finite projective planes of orders 6 and 10 has been proven using computer-assisted proofs
• The existence and asymptotic behavior of $t$-designs for large $t$ is an active area of research
• Quasi-symmetric designs are a generalization of symmetric designs with two block intersection numbers
• Substructures of designs, such as arcs, ovals, and hyperovals in projective planes, have been extensively studied
• Association schemes and coherent configurations provide a unifying framework for studying highly regular combinatorial structures, including designs
• The Hadamard conjecture posits that Hadamard matrices exist for all orders divisible by 4, with implications for the existence of certain symmetric designs
• Efficient algorithms for design isomorphism and automorphism group computation are of practical and theoretical interest
• Applications of designs in quantum information theory, such as measurement schemes and entanglement-assisted error correction, are an emerging area of research