Combinatorial design

Combinatorial design theory is a part of combinatorial mathematics. It studies how to create and understand systems of small groups with special patterns. This area looks at how these groups can be arranged to follow general rules.

Combinatorial design theory is useful in designing experiments, especially in biology and other sciences. It began with the work of statistician Ronald Fisher. 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 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 special rules. Each person must be in at least one group. Every two people must be together in exactly one group. Also, any two groups must share exactly one person. No group can include 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. When these groups can be made, they are called finite projective planes. This shows 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 been used since very old 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. It did this by choosing 4 substances from 16 different ones using a magic square.

These designs grew as people studied combinatorics in the 1700s and 1800s. They included ideas like Latin squares and Steiner systems. People liked to use them in fun math puzzles, such as Kirkman's schoolgirl problem. They were also useful for real things like planning round-robin tournaments. In the 1900s, they became important for design of experiments. This included areas like finite geometry and algebraic statistics.

Fundamental combinatorial designs

Combinatorial design theory studies special ways to arrange sets of items. One important type is called balanced incomplete block designs (BIBDs). In these designs, items are grouped into blocks so that each pair of items appears together a certain number of times.

Another type is symmetric BIBDs. In these, the number of items equals the number of blocks. These designs are related to Latin squares. Latin squares are grids where each symbol appears exactly once in each row and column.

Other important ideas include resolvable BIBDs, where blocks can be grouped in special ways, and difference sets, which help create symmetric designs. Hadamard matrices are special square grids with +1 and -1 values. They connect to designs called Hadamard 2-designs. Pairwise balanced designs (PBDs) make sure that every pair of items appears together a certain number of times in subsets.

These designs are useful 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.
• 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.
• 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.
• 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 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.
• Quasi-3 designs: These are symmetric designs with specific intersections.
• 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.