Hot answers tagged

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


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


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 $v=p^2+...


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

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

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


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

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

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

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

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

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

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

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

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


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 + q^2 ...


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

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


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

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

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

It is not possible to make more than two Fano planes on the same seven points that don't share any line. If one of them is the standard numbering (where three points are collinear iff their bitwise XOR is 0): 4 1 2 7 5 3 6 then the complete set of planes that are compatible with this (up to automorphisms of each plane) is 3 3 ...


3

Any set of two pairwise disjoint Fano planes is maximal; three or more Fano Planes must share at least one line. Henning's answer is streets ahead in terms of succinctness (and quite clever to boot), but frankly, I didn't do all of this work not to post an answer :) But before I launch into a tedious case-by-case proof that there do not exist $3$ or more ...


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

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

I do not think there was ever much hope that Bruck-Ryser-Chowla would be a necessary and sufficient condition for the existence of a symmetric design in general. For projective planes, everything is more strongly constrained, and it was possible to be more optimistic. So it would have been quite reasonable to believe that BRC was sufficient for projective ...


2

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


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



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