On the size of the minimum critical set of a Latin square

Details On the size of the minimum critical set of a Latin square On the size of the minimum critical set of a Latin square

2006-12-31

arxiv.org/abs/math/0701015v1

Journal of Discrete Mathematics. 293(1-3) (2005) pp. 121-127

Mathematics

Combinatorics

Scientific paper

A critical set in an $n \times n$ array is a set $C$ of given entries, such that there exists a unique extension of $C$ to an $n\times n$ Latin square and no proper subset of $C$ has this property. For a Latin square $L$, $\scs{L}$ denotes the size of the smallest critical set of $L$, and $\scs{n}$ is the minimum of $\scs{L}$ over all Latin squares $L$ of order $n$. We find an upper bound for the number of partial Latin squares of size $k$ and prove that $$n^2-(e+o(1))n^{10/6} \le \max \scs{L} \le n^2-\frac{\sqrt{\pi}}{2}n^{9/6}.$$ % This improves a result of N. Cavenagh (Ph.D. thesis, The University of Queensland, 2003) and disproves one of his conjectures. Also it improves the previously known lower bound for the size of the largest critical set of any Latin square of order $n$.

Affiliated with

Also associated with

No associations

Rating

On the size of the minimum critical set of a Latin square does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the size of the minimum critical set of a Latin square, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the size of the minimum critical set of a Latin square will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-294026