ICANEWS

Natural Sciences

Critical Sets in Latin Squares: Bounds, Constructions, and Computational Analysis

This research focuses on critical sets within Latin squares and associated combinatorial structures. A critical set in a Latin square of order $n$ is defined as

Overview

This research focuses on critical sets within Latin squares and associated combinatorial structures. A critical set in a Latin square of order $n$ is defined as a subset of entries in an $n \times n$ array that uniquely determines precisely one Latin square of order $n$. A further condition for a critical set is that the deletion of any single entry from the set results in a sub-array that can be embedded in more than one Latin square of order $n$. The cardinality of the largest critical set in any Latin square of order $n$ is denoted by $lcs(n)$.

Research Context

Prior work by Curran and van Rees in 1978 established an upper bound for the largest critical set, demonstrating that $lcs(n) \leq n^2-n$. This ongoing research builds upon this foundational understanding by deriving new bounds and exploring structural properties of critical sets and related constructs such as intercalates and Steiner trades.

Approach

The research synthesizes theoretical derivations with computational methods across several distinct chapters. Chapter 4 is dedicated to the derivation of an improved upper bound for $lcs(n)$. Chapter 5 provides an analysis of intercalates, establishing new bounds for their maximum number in Latin squares of specific orders ($2^\alpha m$ and $2^\alpha m+1$), and presents a new lower bound for $lcs(4m)$. Chapter 6 details a constructive proof demonstrating the existence of a critical set of a specific size under certain conditions. Chapter 7 examines Steiner trades, employing computational results to classify those trades with a volume no greater than nine where the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Finally, Chapter 8 utilizes extensive computational routines to identify and characterize all critical sets of various sizes within Latin squares of order at most six.

Findings

  • Chapter 4 demonstrates that $lcs(n) \leq n^2-3n+3$.
  • Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders $2^\alpha m$ and $2^\alpha m+1$.
  • Chapter 5 also establishes a new lower bound on $lcs(4m)$.
  • Chapter 6 presents a construction verifying the existence of a critical set of size $\displaystyle{\frac{n^2}{4}} + 1$ when $n$ is even and $n\geq 6$.
  • Chapter 7, through computational results, identifies Steiner trades of volume less than or equal to nine for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges.
  • Chapter 8, using extensive computational routines, identifies all critical sets of different sizes in Latin squares of order at most six.

Key Findings