Timeline for Enumerating subsets with no triple appearing together more than once
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2022 at 18:36 | comment | added | Benjamin Dickman | @LouisD It was asked on behalf of an artist; the formulation of the question as it came to me (which essentially contains all the background information that I have) can be found here: pbs.twimg.com/media/FLh0W2-X0AAFcxr?format=jpg&name=large | |
| Feb 14, 2022 at 18:31 | comment | added | Louis D | Out of curiosity, can you tell us more about the real-world application? | |
| Feb 14, 2022 at 3:49 | history | became hot network question | |||
| Feb 14, 2022 at 1:27 | comment | added | David E Speyer | By computer. I had Mathematica add up all 4-tuples of distinct elements in the abelian group I listed and count which sum was most frequent; the most frequent was the zero element of the group, which occurred 2318 times. (I hope there are no errors.) | |
| Feb 14, 2022 at 0:30 | vote | accept | Benjamin Dickman | ||
| Feb 14, 2022 at 0:03 | answer | added | Max Alekseyev | timeline score: 9 | |
| Feb 13, 2022 at 22:32 | comment | added | Benjamin Dickman | @DavidESpeyer what is meant by "now achieved at the zero element" in your latter comment? (also, in your earlier comment... what motivated the choice of 2 as the remainder, in particular? + did you enumerate the 2290 by program or count by hand?) thanks! | |
| Feb 13, 2022 at 21:45 | comment | added | David E Speyer | Using $\mathbb{Z}/5 \mathbb{Z} \times (\mathbb{Z}/2 \mathbb{Z})^3$ instead of the cyclic group of order $40$ improves the lower bound to 2318 (now achieved at the zero element). | |
| Feb 13, 2022 at 21:37 | comment | added | Benjamin Dickman | @LSpice I had initially omitted the condition that each subset should have size $4$ | |
| Feb 13, 2022 at 21:35 | comment | added | Benjamin Dickman | thanks for the comments & yes @DavidESpeyer I've edited to include the condition that each subset has $4$ elements; RE: $J(40,4)$ I'm not sure whether this means the problem at hand, in particular, may be intractable; also, if that means another tag should be added e.g. around graph theory, then by all means! (The steiner-triple-system one could go if multiple tags are worth adding...) | |
| Feb 13, 2022 at 21:32 | comment | added | David E Speyer | Another way to rephrase this problem is that you are looking for the largest anticlique in the Johnson graph $J(40,4)$. Wikipedia tells me that determining the chromatic number of Johnson graphs is open, which makes me suspect the situation for anticliques will be just as bad. en.wikipedia.org/wiki/Johnson_graph | |
| Feb 13, 2022 at 21:31 | history | edited | Benjamin Dickman | CC BY-SA 4.0 |
including omitted constraint per DES comment
|
| Feb 13, 2022 at 21:25 | comment | added | David E Speyer | As a lower bound, $\{ \{ a,b,c,d \} : a+b+c+d \equiv 2 \bmod 40 \}$ has 2290 elements, and clearly has no two elements which overlap in size three; this is not too far from the ratio of binomial coefficients, which gives 2470. | |
| Feb 13, 2022 at 21:20 | comment | added | David E Speyer | You write "Given a set of 40 elements, what is the maximum number of subsets that can be created such that no triple appears more than once?" Given the context in the rest of the question, do I gather correctly that you meant to include the additional condition that each subset has $4$ elements? | |
| Feb 13, 2022 at 21:02 | comment | added | LSpice | Is it correct to rephrase this question as: What is the maximum size of a family $\mathcal F \subseteq \binom{\mathbf n}p$ (writing $\binom{\mathbf n}p$ for the set of $p$-element subsets of an $n$-element set $\mathbf n$) such that $\lvert A \cap B\rvert$ is strictly less than $q$ for all $A, B \in \mathcal F$? | |
| Feb 13, 2022 at 20:56 | history | edited | Benjamin Dickman |
added ref-req tag
|
|
| Feb 13, 2022 at 19:49 | history | asked | Benjamin Dickman | CC BY-SA 4.0 |