

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.
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.
a(9) >= 45.  Richard Bean, 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


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, arXiv:math/0107159 [math.CO], 2001.
Richard Bean and Ebadollah S. Mahmoodian, A new bound on the size of the largest critical set in a Latin square, Discrete Math., 267 (2003), 1321.
Mahya Ghandehari, Hamed Hatami and Ebadollah S. Mahmoodian, On the size of the minimum critical set of a Latin square, arXiv:math/0701015 [math.CO], 2006.
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, arXiv:math/0701014 [math.CO], 2006; 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,more


AUTHOR

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


STATUS

approved



