See http://oeis.org/A090245 Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Apr 2, 2015 at 4:31 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
I think the best paper about this is the one by Diane Maclagan and Ben Davis, which I edited for the Intelligencer (MI 25#3, 2003).
http://homepages.warwick.ac.uk/staff/D.Maclagan/papers/set.pdf
The asymptotic size of the largest line-free subset of (F_3)^n is definitely q^n for some q, but the bounds on q are pretty poor. In particular, the paper says it is an open question whether q=3, and as far as I know, that is still the case.
--Michael
On Thu, Apr 2, 2015 at 4:13 PM, Dan Asimov <asimov@msri.org> wrote:
The game called "Set", in case you don't know, is a deck of 81 cards, each one having a visual image on it.
The image displays 4 characteristics, each of which is a choice of one of 3 possible versions.
The characteristics happen to be: Color, Number, Shape, and Shading.
Color = {Red, Green, Purple}; Number = {One, Two, Three}; Shape = {Oval, Diamond, Squiggle}; Shading = {Light, Medium, Heavy}.
All of which details are irrelevant to the math behind it.
We may as well assume the 81 cards is the vector space
V = (F_3)^4
of dimension 4 over the field of 3 elements.
The goal of the game is to find affine lines in V, namely subsets of the form
L + v
where L is any 1-dimensional subspace of V and v is any element of v. These are all, of course, subsets of size 3.
DIFFICULT PROBLEM: What is the largest size of a subset of V that contains no affine line?
The answer is 20. Every known proof of this is a tedious case-by-case analysis or else by computer search.
GENERALIZED DIFFICULT PROBLEM: Let V_n denote the vector space (F_3)^n. What is the largest size of a subset of V_n containing no affine line?
Let M(n) denote this number: the maximum size of any subset of V_n containing no affine line.
Apparently even the n=5 case borders on being too large for computers to handle in any reasonable time, but that has been solved. In fact, here is what is known:
n 1 2 3 4 5 6 7+
M(n) 2 4 9 20 45 112-114 ?
----------------------------------------------------------
QUESTION: Is there a nice asymptotic expression for M(n) ?
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun