Tag Info

Hot answers tagged

9

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

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


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


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

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

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


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

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

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

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

$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

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

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

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


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

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

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

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

Since $v$ is being used to denote the cardinality of $V$, I’m going to use $x$ and $x_0$ for elements of $V$. Let $\mathcal{T}$ be the collection of all $2$-element subsets of $V$, and let $x_0$ be some fixed element of $V$. Then we’re counting $$\mathcal{P}=\{\langle T,B\rangle\in\mathcal{T}\times\mathcal{B}:x_0\in T\subseteq B\}\;,$$ the set of all ...


2

The adjacency matrix of a symmetric block design satisfies $AA^T=(r-\lambda)I+\lambda J$ and $JA=AJ=kJ$. An Hadamard matrix $H$ satisfies $HH^T=nI$. So now let us count $BB^T$: $$ BB^T=(2A-J)(2A-J)^T=4AA^T-2AJ-2JA+JJ^T=4((r-\lambda)I+\lambda J)-4kJ+vJ. $$ Thus, $BB^T=4(r-\lambda)I+[4(\lambda-k)+v]J$. Therefore $B$ is Hadamard if the coefficient of $J$ is ...


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

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

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

"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

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


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


2

Figured it out. ${4 \choose 2} = 6$, ${3 \choose 2} = 3$, ${8 \choose 2} = 28$.



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