

A063437


Cardinality of largest critical set in any Latin square of order n.


1




OFFSET

1,3


COMMENTS

A critical set in an n X n array is a set C of given entries such that there exists a unique extension of C to an n X n Latin square and no proper subset of C has this property.
a(9) >= 45.  Richard Bean (rwb(AT)eskimo.com), May 01 2002
For n sufficiently large (>= 295), a(n) >= (n^2)*(1(2 + log 2)/log n) + n*(1 + (log(8*Pi)/log n)  (log 2}/(log n). Bean and Mahmoodian also show a(n) <= n^2  3n + 3.  Jonathan Vos Post, Jan 03 2007


REFERENCES

Richard Bean and E. S. Mahmoodian, A new bound on the size of the largest critical set in a Latin square, Discrete Math., 267 (2003), 1321.
R. Bean and Ebadollah S. Mahmoodian, A new bound on the size of the largest critical set in Latin squares, Discrete Math, to appear.


LINKS

Table of n, a(n) for n=1..6.
Richard Bean and E. S. Mahmoodian, A new bound on the size of the largest critical set in a Latin square
Mahya Ghandehari, Hamed Hatami and Ebadollah S. Mahmoodian, On the size of the minimum critical set of a Latin square, Journal of Discrete Mathematics. 293(13) (2005) pp. 121127
Hamed Hatami and Ebadollah S. Mahmoodian, A lower bound for the size of the largest critical sets in Latin squares, Bulletin of the Institute of Combinatorics and its Applications (Canada). 38 (2003) pp. 1922


CROSSREFS

Sequence in context: A072456 A138659 A020590 * A190711 A210977 A049792
Adjacent sequences: A063434 A063435 A063436 * A063438 A063439 A063440


KEYWORD

nonn


AUTHOR

Ahmed Fares (ahmedfares(AT)mydeja.com), Jul 24 2001


EXTENSIONS

The next terms satisfy a(7) >= 25, a(8) >= 37, a(9) >= 44, a(10) >= 57. In the reference it is proved that, for all n, a(n) <= n^2  3n + 3.


STATUS

approved



