2
$\begingroup$

Most research on cap sets that I'm aware of focuses on the size of a cap set. Are there any results about the number of maximum-cardinality cap sets?

For example, it is known that in the game of SET, the maximum cardinality of a cap set (i.e., a SET-free collection) is 20. According to Wikipedia, Donald Knuth found in 2001 that there are 682344 cap sets of cardinality 20[citation needed]. Are there any nontrivial upper and lower bounds known in general? Typing 682344 into OEIS does not yield any relevant hits.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ On the needed citation, see Knuth's CWEB programs setset.w (February 2001) and setset-all.w (March 2001). (Note that CWEB programs are meant to be read as typeset PDFs by running them through the CWEAVE utility.) The number 682344 doesn't show up in those programs. (In fact, it shows up on Wikipedia on 31 Dec 2017). Perhaps the attribution was because of ams.org/publicoutreach/feature-column/fc-2015-08. $\endgroup$
    – ho boon suan
    Commented Apr 16 at 3:08
  • 3
    $\begingroup$ the answer should be the same as for this question: mathoverflow.net/questions/464314/…. let $r_3(\Bbb{F}_3^n)$ denote the size of the largest capset in $\Bbb{F}_3^n$. $2^{r_3(\Bbb{F}_3^n)}$ is an obvious lower bound, and by hypergraph containers we ought to have an upper bound of $2^{C r_3(\Bbb{F}_3^n)}$ for some $C$. $\endgroup$
    – Zach Hunter
    Commented Apr 16 at 4:03
  • 3
    $\begingroup$ and the reason why containers should work is because you can construct capsets which are larger than what probabilistic deletion method gives. $\endgroup$
    – Zach Hunter
    Commented Apr 16 at 4:07

1 Answer 1

Reset to default
1
$\begingroup$

Check out the paper "Counting SET-free sets" by Nate Harman at https://arxiv.org/abs/1604.07811

EDIT: As mentioned in the comments, this answers a slightly different question than what Timothy asked.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Unfortunately my stuff there doesn't quite get at what he wants. There I was looking at SET-free sets of a fixed size, but in games with an increasing number of attributes. There was some nice algebraic structure there, but those methods unlikely to say anything about the extremal case. $\endgroup$
    – Nate
    Commented Apr 15 at 20:55
  • $\begingroup$ Whoops, okay, well I'll leave this up as possibly relevant although not answering the question. $\endgroup$
    – Sam Hopkins
    Commented Apr 15 at 20:56
  • 2
    $\begingroup$ Oh it's definitely connected. One might notice that this paper came out just a few months before the Ellenberg-Gijswijt paper -- I was definitely trying to get at the cap-set problem this way but ultimately concluded it couldn't work. $\endgroup$
    – Nate
    Commented Apr 15 at 20:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .