# Tag Info

6

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

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). ...

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

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 ...

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

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

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 ...

3

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 ...

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

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

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

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, ...

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

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

This is unfamiliar territory for me, but here’s something that should at least get you started. Fix a non-identity element $g\in G$; $g=d_1d_2^{-1}$ iff $gd_2=d_1$, so $|gD\cap D|=\lambda$. Thus, $|gD\cap D|=\lambda$ for each $g\in G\setminus\{1_G\}$. Let $E=G\setminus D$. Then for any $g\in G\setminus\{1_G\}$ we have gE\cap E=(G\setminus ...

2

Your answer to the first question is fine. Your answer to the second question has problems. First, $\binom{10}3=120$. Second, subtracting $10$ pairs from $\binom{10}3$ triples makes no sense. What you want to subtract is the number of triples, at least two of whom are sitting beside each other. There are two different kinds of bad triples, which you have to ...

2

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. ...

2

You can hold each lecture at each hour for three hours. This will allow you to finish the event in 3 hours, but you will have to add the following constraints: Each lecture can only be attended by 75 participants. Thus, some participants may not get to attend the first three choices. There can only be 25 people to attend each lecture each hour. This may ...

2

Suppose that lecture 1 takes place in room 1, lecture 2 in room 2, etc. and the lectures do not change rooms between hours. Suppose that persons 1 through 25 go to lecture 1 the first hour, 26 through 50 go to lecture 2 the first hour, etc. Then persons 1 through 25 go to lecture 2 the second hour, persons 26 through 50 go to lecture 3, and persons 101 - ...

2

How about you read the paper that he wrote! Tarry, G. Le probleme des 36 officiers. Comptes Rendus Assoc. France Av. Sci. 29, part 2: 170–203, 1900

2

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 ...

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

"The bible" of algebraic graph theory is essential: Distance-Regular Graphs by Brouwer, Cohen and Neumaier. Another favorite of mine is Permutation Groups by Peter Cameron.

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 ...

1

Since your after remarks, here's some. It's easy enough these days to prove the non-existence on a computer. There are only $12$ main classes to exclude (ref.). There's a short proof of this result: Stinson, A short proof of the nonexistence of a pair of orthogonal latin squares of order six, J. Comb. Theory A, 36 (1984) 373-376 There's a recent ...

1

Arranging the integers from $0$ to $99$ in a $10\times10$ square in such a way that no two in the same row or column have the same first digit or the same second digit. It can be seen as a pair of orthogonal latin squares of order $10$: the first digits form one square, the second digits the other. Source: quick google search for the first row. See this ...

1

This question asks to find a edge covering of the complete graph $K_{12}$ using $7$ copies of $3K_4:=K_4 \cup K_4 \cup K_4$. There are $\binom{12}{2}=66$ edges in $K_{12}$ and $7 \times 3 \times 6=126$ edges in the $7$ copies of $3K_4$. The above suggests the "best possible" might be when $6$ edges occur once and the other $60$ occur twice. But this is ...

1

I think Lissajous_curves are cool. But that's just me.

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