How has information theory created new combinatorial problems?

Information theory has significantly influenced combinatorics by introducing new classes of problems, particularly through the development of coding theory.1

A primary area where these fields intersect is the construction of error-correcting codes. This involves the combinatorial "packing problem," which seeks to construct an $n\times r$ matrix $H$ with the property $P_t$—meaning any $t$ rows are linearly independent—to maximize the number of rows $n$ for a given $r$ and field size $q$. Such matrices are essential for creating codes where a vector $c^{\prime }$ is a code word if $c^{\prime }H=0$, allowing for the detection and correction of transmission errors.2

The challenge of finding the maximal number of rows, denoted as $n_t(r,q)$, remains a significant combinatorial problem. While general solutions exist for specific cases, such as the one-error-correcting codes of Richard W. Hamming ($t=2$), the optimal values for larger parameters remain unknown. These problems are vital not only for communication theory but also for the design of factorial experiments.21