46 votes
Accepted

"The Two Sheriffs" puzzle

Here's a solution for the case of seven suspects that uses the Fano plane. Let the seven points of the Fano plane represent the seven suspects. Alice and Bob both reveal the name of the suspect ...
  • 5,818
37 votes
Accepted

What is the name of this combinatorial object and place to read about it?

What you're asking for is a code with two non-usual restrictions. It's a code over alphabet size $d$. You want each code word to have length $pd$ and you want to have $qd$ total code words. The ...
  • 2,610
29 votes

Is there a Kolmogorov complexity proof of the prime number theorem?

Firstly, the proof given there doesn't really show that $p_n = O(n(\log n)^2)$ (at least not without further effort). Instead what it shows is that there are $n$ for which $p_n = O(n(\log n)^2)$, ...
  • 42.6k
24 votes
Accepted

Hamming distance to primes

See OEIS sequences A067760 and A076336. If $n$ is a dual Sierpiński number, there is no $k$ such that $n+2^k$ is prime. There is no prime with Hamming distance $1$ to the Sierpiński number $2131099$, ...
12 votes
Accepted

Is this graph 3-colorable?

If I constructed the graph correctly, according to a program the chromatic number is $4$, so the graph is not 3 colorable. The program is: https://code.google.com/p/graphcol/ Got the same result ...
  • 23.6k
11 votes

A question on representation of graphs

It's important to clarify what definition of "cycle" you have in mind. In algebraic-graph-theory contexts like this one, the natural definition is that it's a set of edges with even degree at each ...
11 votes
Accepted

When can this condition on linear codes be satisfied?

Any maximal $r$-separated set is an $r$-net, otherwise you can augment it with a non-covered point. But the same holds for linear codes! If a subspace $V$ is $r$-separated but not an $r$-net, you may ...
11 votes
Accepted

Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

If the Hamming distance between $A$ and $B$ is at least $d$, it yields that $B$ is disjoint from the $(d-1)$-neighborhood of $A$. By isoperimetric inequality for a Boolean cube (Harper's theorem), the ...
  • 90.4k
9 votes
Accepted

Is primality essential in Varshamov's bound?

The analogue of the Varshamov inequality need not hold for instance for $\lvert\Sigma\rvert=q=6$: For $n=4$ and $d=3$ it would give a code $C\subseteq\Sigma^4$ with $d(C)\ge3$ and $\lvert C\rvert=36$. ...
9 votes

Characterization of metrics such that the volume of balls doesn't depend on their centers?

I do not know the answer in general, but in the case in which $X$ is a subset of $\mathbb{R}^n$ there are some known remarkable results: If $X\subset\mathbb{R}^2$ is bounded, then $X$ consists of ...
9 votes

The chromatic number of the union of two graphs

This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$. Observation 1. $\chi(G_n)\ge\left\lfloor\...
  • 8,771
8 votes
Accepted

What measurable quantity can constrain the number of odors human can discriminate?

Suppose $\Omega = \{0,1\}^{128}$ is partitioned into $N$ different sets $S_j$, with $|S_j|/|X| = p_j$. Suppose you take $n$ random pairs of points of $\Omega$ and see how many of these pairs can't be ...
8 votes

A question on representation of graphs

I have now tried a few different strategies which are all winding up at $d \approx n \log_2 n$. I'll describe the simplest of these. (David Epstein's strategy with the spanning tree gives $d \approx n^...
8 votes
Accepted

How did they come up with the MRRW bound?

For linear programming type bounds it is sometimes only possible to give effective bounds (that is bounds that work and are manageable) and what is surprising is that the primitive method often gives ...
  • 3,104
8 votes

Is there a Kolmogorov complexity proof of the prime number theorem?

I think it’s not uncommon for arguments in elementary number theory to be “philosophically” information-theoretic in nature. But this is not a very deep fact - at the end of the day it all comes down ...
  • 2,166
8 votes

The chromatic number of the union of two graphs

In a similar vein to $\chi^{\ast}(G_n)$, we can define a quantity $\chi^{\ast \ast}(G_n)$ as follows: Suppose you have an abelian group $M$ and a set $S=\{x_1, x_2, \dots, x_n\}\subset M$, such that ...
7 votes
Accepted

lower bound on A(k,4,floor(k/2))

A better bound than that is known. Define a function $f:\{0,1\}^n\to \{0,1,\dots,n-1\}$ as follows: $$ f(c_0,c_1,\dots,c_{n-1})=\left(\sum_{i=0}^{n-1} i\cdot c_i\right)\bmod n.$$ Then define the ...
7 votes
Accepted

Maximal neighbour-full partition of $\{0,1\}^n$

If I understand correctly I think the question can be re-phrased as follows, what is the largest complete minor of the $n$-dimensional hypercube? To see this we note that any partition into $k$-sets ...
7 votes
Accepted

Codes with a twisted cyclic action

This is an extended comment that may be too long for the comment section. If I understand your question correctly, the linear codes you described are automatically trivial. Define $\pi_{c}$ to be ...
6 votes
Accepted

An isoperimetric problem on the hypercube

When A consists of even vectors only, the problem was probably solved by Korner and Wei [Odd and even Hamming spheres also have minimum boundary, Discrete Math. 51 (1984), 147–165]. See also Lemma 1....
6 votes

A question on representation of graphs

Here is a modest improvement on the upper bound that shows $d=O(n\log\log n)$. The base of the construction is the following. Order the vertices according to some permutation as $v_1,\ldots,v_n$. Fix ...
  • 17.4k
6 votes
Accepted

Need help with paper written in Russian... Yorgov's paper on self-dual codes with automorphisms of odd order

According to MathSciNet, a translated version of the paper is available in the journal Problems of Information Transmission ISSN: 0032-9460. Your local librarian should be able to help you track down ...
  • 32.1k
6 votes
Accepted

How to quantify the error correction capacity of LDPC code?

It is a difficult problem to find the minimum distance of an LDPC. Vardy shows in The Intractability of Computing the Minimum Distance of a Code that it is NP-hard to find the minimum distance. ...
6 votes

Application of simple Lie algebras over finite fields

Fourier transform of invariant functions on finite reductive Lie algebras have been developed in here: http://www.springer.com/de/book/9783540240204 This can be considered the Lie algebra analogue of ...
6 votes
Accepted

Enumeration of field generators of a finite field over $\mathbb{F}_{q}$, which are $m^{th}$ powers in the same field

$$| S \cap S^m | = \sum_{n|d} \mu(n) \frac{ \gcd ( m (q^{d/n}-1), q^{d}-1 )}{ \gcd (q^{d} - 1, m) } $$ First note that $|S \cap S^m | = |S \cap \mathbb F_{q^d}^m |$ because every $m$th power that ...
  • 119k
6 votes
Accepted

Guessing the number of other $1$'s in a binary sequence

Since every person knows his assigned digit, the problem is equivalent to guessing the sum of all digits. Label the persons with $0,1,...,n$. Let person $0$ guess $0$ when given a $0$, and $n+1$ when ...
  • 8,566
5 votes

Minimally intersecting subsets of fixed size

This is a coding theory question. You want to find a binary constant weight $m$ code with $k$ codewords, and of maximal possible distance. There was a lot of research done on this. For the specific ...
5 votes

The chromatic number of a Hamming-related graph

This is pretty late, but there is a result by Frankl and Rodl (Theorem 1.11 from http://www.renyi.hu/~pfrankl/1987-3.pdf) that shows that the graph on $\mathbb{F}_2^n$ (for $n$ a multiple of four) ...
5 votes
Accepted

Effects of many degree-2 variable nodes in the Tanner graph during the decoding of LDPC codes

As maybe you know, the most good decoding algorithm for LDPC codes, for example iterative decoding, has not provable efficiency, except in special cases. But, it is believed that variable nodes with ...
  • 4,658
5 votes

How to quantify the error correction capacity of LDPC code?

As @John mentioned, there is not general way and nice formula for computing the minimum distance of codes. The problem remain difficult for LDPC codes as like as other codes. But, there are several ...
  • 4,658

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