# Tag Info

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

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

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

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

• 141k
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

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

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

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

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

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

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