# Tag Info

11

I do not know about photographic memory, but I found this quite appealing way to describe it: The girls are represented as points and the groups as paths. Each group contains three girls and no two girls belong to the same group on different days. I found the description of it on this website and made the above animation of it. BTW: Just a few ...

11

There is a difference between the projective plane as an object of algebraic geometry and as a combinatorial construction (=Steiner system) that has not been adequately explained. The former makes sense over any field - the latter only over a finite field (together with the speculations that no field may be necessary for the required construction to exist). ...

7

As discussed in the comments, your three conditions imply that the system of sets is a finite projective plane. First I'll give a construction of projective planes of prime order. The explanation follows. Construction. Let $p$ be a prime. The finite field $\mathbf{F}_p$ is the set $\{0,1,2,\ldots,p-1\}$ with arithmetic performed modulo $p$. Let ...

5

I assume here (although you should really specify) the following meanings for the parameters: $v$ is the number of elements in your ground set. $r$ is the number of blocks containing a given element $k$ is the number of elements in each block. $\lambda$ is the number of blocks containing each pair of elements. Assuming that this is correct: notice that ...

5

You are looking for the covering code number $K_4(4,1)$. Finding such numbers are very hard problems in general. This particular one can be found in this paper, and it is equal to 24. The covering table is also given, I reproduce it here: AAAA AABB ABAB ABBA ACCC ADDD CACD CCDA CDAC DDCA DADC DCAD BAAB BABA BBAA BBBB BCCC BDDD CBCD CCDB CDBC DDCB DBDC ...

5

You take $\Gamma = K_{5}$, and consider the edges of $\Gamma$ to be the points of your design. Then you have some specified subgraphs, given in the picture on page 2 that you refer to, they all have $4$ edges. The blocks of your design are the subgraphs of $\Gamma$ that are isomorphic to one of these specified subgraphs. (considered as sets of edges). For ...

4

Short answer: plane geometry mod $2$. A longer answer: There are two different facts in play here. One is that this type of combinatorial construction is called a block design and is in fact a more special type of design called a finite geometry. It is similar to, but more general than, the geometry of points and lines, and the terminology is borrowed ...

4

I haven't come up with a general construction yet, but I believe the answer is $n=k^2-k+1$. I will prove that $n \leq k^2-k+1$. I will edit in the construction in a while when I get it. WLOG let $A_1=\{1, 2, \ldots , k\}$, and let $x_a$ be the number of $j \not =1$ such that $a \in A_j$, where $1 \leq a \leq k$. Observe that if $x_a \geq k$, then WLOG let ...

4

E.Bannai, T.Ito, Algebraic combinatorics I: Association schemes. Benjamin/Cummings Publishing Co., 1984. R.L.Graham, M.Grötschel, L.Lovász, Handbook of combinatorics (vol. 1). Elsevier, 1995 . H.Lüneburg, Tools and fundamental constructions of combinatorial mathematics. BI-Wiss.-Verl., 1989.

4

Which combinatorial structures different from graphs are interesting for symmetry investigations? Probably all of them. The next ones that come to my mind are: Association schemes Combinatorial designs Block codes Finite geometries Lattices Matroids etc. There are many connections between the different areas. For example, linear codes are the same as ...

4

I'll try to give a basic idea of how these are used in exploratory medical research. Traditional medical experiments: Patients are given a single candidate treatment and are observed for a given response (i.e. dose-response). If the response is statistically significant, then it is considered for further studies, and possibly may end up on the market. ...

3

Tarry's paper is available in digitized form at the online French National Library, http://gallica.bnf.fr/ as well as many volumes of 19th and early 20th century scientific journals. Here is a link for the first page: http://gallica.bnf.fr/ark:/12148/bpt6k2011936/f175.image It is quite a long paper (34 pages) investing potential cases sorted according to ...

3

Set up the standard incidence matrix. Let the row be the $n$ participants and the 14 columns be the languages. Fill in the entry of 1 if the participant can speak the language. We wish to count the number of column triples $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$. Since every 3 participants speak a common language, this number is at least $n \choose ... 3$n ≥ 3$participants, 14 languages are spoken. We know that: - Any$3$participants speak a common language. - No language is spoken by more than$\frac{1}{2}$of the participants. What is the least value of$n$? The numbers,$(14,3,\leq 1/2)$, can be understood from geometry over finite fields. They are suspiciously close to the case of$15 = q^3 + ...

3

First of all, such kind of questions are very hard to answer exactly, in particular, if the set of possibilities is so huge as in your case. However, there is a standard method to derive an upper bound on the maximum size. I will compute this upper bound in this answer. Your question can be reformulated: What is the maximum size of a set $X$ of mixtures, ...

3

According to one of the Wikipedia editors: The primal graph of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge. The primal graph is sometimes also known as the Gaifman graph of the hypergraph.

3

We can follow @Ivan's answer, to give a construction with $k(k-1)+1$ sets. It was shown that each element cannot be present in more than $k$ sets, this construction has each element occurring in exactly $k$ sets. Let $A_1 = \{1,2,\ldots ,k\}$. Let the next $k-1$ sets $A_2, A_3, \ldots , A_k$ contain element $k$. As they all now have a common element $k$, ...

3

This is a tough nut to crack (or, more likely, I'm looking at it all wrong). Anyway, I think I found a promising way to look at it. Conjecture. It is impossible to cover all the points of the punctured plane $\Bbb{F}_5^2\setminus\{(0,0)\}$ by seven lines, none passing through the origin. This is just a conjecture. I think it's true, but I'm not betting a ...

3

I see no reason to assume that the number of elements is divisible by $3$; so I'll work with $m$ elements, where $m$ is your $3n$. This answer has gone through a lot of edits; I now have a complete answer for all $m$. For $m \equiv 1$ or $3 \bmod 6$, the answer is $(m^2-m)/6$. For $m \equiv 5 \bmod 6$, the answer is $(m^2-m-8)/6$. For $m$ even, the answer ...

3

Four: ABC DEF GHI ADG BEH CFI AEI BFG CDH AFH BDI CEG We know this to be maximal: at the end, everyone is acquainted with everyone, so no improvement is possible. For other $n$, I'm not exactly sure what we can do. It's clear that for $n=2$ we only get one matching, because any trio will now be guaranteed to have a pair from one or the other original ...

3

What you are asking about are called covering designs. A more standard notation in combinatorics defines $(v,k,t)$-covering design to mean: $v =$ total number of points (your universe N) $k =$ size of subsets (blocksize, your set size X) $t =$ size of covered combinations (your K elements) There is a special case where each t-subset is covered ...

3

This is part of what's called "combinatorial design theory". In your case you can think of this as designing a round-robin tournament - the sort of tournament where everybody plays everybody - except you can cut it off after 14 rounds. If you look at the section "scheduling algorithm" you can find out how to do this. Basically, number your students from 1 ...

3

In a real classroom, the contraints will be time-dependent, including the membership in the class, the size of the class, and who's friends with whom. So a streaming optimization algorithm is the only practical choice - you don't want to lock yourself into a beautiful combinatorial design and then gain a new student 3 weeks into the process. For students ...

2

One idea is to restrict attention to circulant matrices, since they will automatically be commuting. This is so because a circulant matrix is a polynomial in a matrix of the form  \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 ...

2

You could show that there are only four automorphisms fixing $1$, namely, $(2,5)(4,6)$, $(2,6)(3,5)$, $(2,3)(5,6)$ and the identity. These together with $(1,3,5)(2,4,6)$ generate a transitive group (i.e. there is a single orbit), so by the Orbit-Stabilizer Theorem, the full automorphism group $G$ has order $6 \times 4 = 24$. It is not clear what exactly ...

2

There will always exist some 'trivial' designs. For any $k \in K$, define $\mathcal{B}$ as containing $\lambda$ copies of $X$ ($X$ is of size $k$). Clearly each pair of elements is present in exactly $\lambda$ subsets and all subset sizes are contained in $K$.

2

Notice that you are counting isomorphism classes of simple graphs on six vertices in which every vertex has degree three. If there is a triangle in the graph, then one easily sees that the whole graph is Indeed, no two triangles can share an edge, so that is the only possibility. If there is no triangle, let $x$ be a vertex and let $a$, $b$, $c$ be its ...

2

Either two numbers come from $1-7$, or two numbers come from $8-14$.

2

Let $d = 2e + 1$ be the minimum distance of $C$. For all $v\in\{0,1\}^n$, we have $w_{\text{Ham}}(v) = \left|\operatorname{supp}(v)\right|$ and $d_{\text{Ham}}(v,v') = \left|\operatorname{supp}(v) \triangle \operatorname{supp}(v')\right|$, where $\triangle$ denotes the symmetric difference of sets. In the following, we identify a vector $v\in \{0,1\}$ with ...

2

"A person is on exactly two committees" = "An intersection point is in exactly two lines" "A committee contains exactly three people" = "A line contains exactly three intersection points" "No two committees have more than one person in common" = "No two lines cross in more than one place" This sort of solution wouldn't work in the same way if you changed ...

Only top voted, non community-wiki answers of a minimum length are eligible