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

- 51.8k

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

- 18.2k

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

- 19.2k

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

- 16.3k

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

- 23.2k

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

- 51.8k

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

- 141k

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

- 82.5k

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

- 578

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

- 462

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

- 3,622

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

- 76

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

- 7,302

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

- 919

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

- 13k

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

- 1,872

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

#### Related Tags

coding-theory × 268co.combinatorics × 101

it.information-theory × 79

finite-fields × 28

linear-algebra × 25

graph-theory × 23

reference-request × 18

pr.probability × 14

lattices × 12

ag.algebraic-geometry × 11

nt.number-theory × 11

polynomials × 11

discrete-geometry × 11

matrices × 9

mg.metric-geometry × 8

algorithms × 8

computational-complexity × 8

cryptography × 8

computer-science × 7

gr.group-theory × 5

rt.representation-theory × 5

ca.classical-analysis-and-odes × 4

asymptotics × 4

random-matrices × 4

additive-combinatorics × 4