Combinatorial design

Combinatorial design theory is a part of combinatorial mathematics that studies how to create and understand systems of finite sets with special patterns of balance and symmetry. This area looks at how these sets can be arranged so that they follow general rules, even though those rules aren't always very strict. This flexibility lets many different kinds of objects be studied together, whether it's how big the overlaps between sets are, like in block designs, or how numbers are placed in patterns, like in sudoku grids.

Combinatorial design theory is very useful in designing experiments, especially in biology and other sciences. It began with the work of statistician Ronald Fisher when he was studying how to set up biological experiments. Today, this theory helps in many areas, including finite geometry, planning sports tournaments like tournament scheduling, creating fair lotteries, understanding molecules in mathematical chemistry, studying living systems in mathematical biology, designing efficient algorithms, improving networking systems, identifying groups in data through group testing, and even creating secure codes in cryptography. It's a powerful tool that connects many different fields.

Example

Imagine you have a group of people, and you want to organize them into smaller groups or "sets" with very specific rules. Each person must be in at least one group, every two people must be together in exactly one group, and any two groups must share exactly one person. Also, no group can include everyone or almost everyone, and no group can have just one person.

This puzzle only works if the number of people, n, follows a special pattern: q² + q + 1, where q is a prime power. Scientists believe these are the only possible numbers that work, but they are still trying to prove it. When these groups can be made, they are called finite projective planes, showing the connection between finite geometry and combinatorics. For example, when q is 2, the solution is known as the Fano plane.

History

Combinatorial designs have a long history, dating back to ancient times. One early example is the Lo Shu Square, an old magic square. In about 587 AD, a book called Brhat Samhita by Varahamihira from India used these designs to help make perfumes by choosing 4 substances from 16 different ones using a magic square.

These designs grew along with the study of combinatorics in the 1700s and 1800s, including ideas like Latin squares and Steiner systems. They became popular in fun math puzzles, like Kirkman's schoolgirl problem, and in real-life uses such as planning round-robin tournaments. In the 1900s, they were important for design of experiments, including areas like finite geometry and algebraic statistics.

Fundamental combinatorial designs

The core of combinatorial design theory focuses on special arrangements of sets that follow specific rules. These include balanced incomplete block designs (BIBDs), which arrange elements into blocks so that each pair appears together a fixed number of times. Another important type is symmetric BIBDs, where the number of elements equals the number of blocks. These designs are closely related to Latin squares, grids filled with symbols so that each symbol appears exactly once in each row and column.

Other key ideas include resolvable BIBDs, where blocks can be grouped into special partitions, and difference sets, which help create symmetric designs. Hadamard matrices are square grids of +1 and -1 values with useful properties, and they connect to special designs called Hadamard 2-designs. Finally, pairwise balanced designs (PBDs) ensure that every pair of elements appears together in a set number of subsets. These designs have many applications in scheduling and experiments.

Main article: Balanced incomplete block designs (BIBDs)
Main articles: Hadamard matrices and Hadamard designs, Symmetric BIBDs
Further information: Latin rectangle, Mutually orthogonal Latin squares (MOLS), Difference sets, Fisher's inequality, 15 schoolgirl problem, Projective plane, Bruck–Ryser–Chowla theorem, Erdős–De Bruijn theorem

Other combinatorial designs

The Handbook of Combinatorial Designs has many chapters about different types of combinatorial designs. These designs arrange elements in patterns to study balance and symmetry.

Some important types include:

• Balanced ternary designs: These arrange elements into groups with specific rules about how elements appear together.
• Balanced tournament designs: These help schedule rounds in tournaments so each team plays fairly.
• Frequency squares: These are like magic squares where each number appears a certain number of times in each row and column.
• Hall triple systems: These are special arrangements of triples of elements with particular properties.
• Howell designs: These are used in bridge tournaments to organize rounds and tables.
• Lotto designs: These model lottery systems to find the minimum number of tickets needed to guarantee a win.
• Magic squares: These are squares where the sums of numbers in each row, column, and diagonal are the same.
• Mendelsohn designs: These arrange ordered triples of elements with specific adjacency rules.
• Orthogonal arrays: These arrange elements in tables where each combination appears a certain number of times.
• Packing designs: These arrange elements to cover all possible combinations a certain number of times.
• Quasi-3 designs: These are symmetric designs where intersections of blocks have specific sizes.
• Quasi-symmetric designs: These have block intersections with fixed numbers.
• Room squares: These are special square arrays used in design theory.
• Spherical designs: These arrange points on a sphere so that averages of functions match the sphere's averages.
• Turán systems: These are arrangements of edges in graphs with specific properties.
• Tuscan rectangles: These arrange symbols in rows so that each pair appears in specific positions.
• t-wise balanced designs: These ensure every group of t elements appears together a certain number of times.
• Weighing matrices: These help estimate weights of objects in experiments.
• Youden squares: These are rectangular arrays used in experimental design.

Each design has unique rules and applications in mathematics and real-world problems.