Expectation of edge weights on the complete graph

Question

Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random binary string of length $k$ with equal probability. For each vertex $v$ let $b(v)$ denote the attached binary string. For a binary string $b$, let $x_0(b)$ denote the number of zeroes in $b$ and $x_1(b)$ be the number of one's in $b$. For each pair of vertices $u,v$ put

$$w(\{u,v\}) = \max\{x_0(b(u) + b(v)), x_1(b(u)+b(v))\}$$

Here summation of two binary strings of length $k$ is to be interpreted as summing two elements of $\mathbb{F}_2^k$, say.

Let $X_{n,k}$ denote the random variable

$$X_{n,k} = \max \{ w(\{u,v\}) : u,v \in V(K_n)\}.$$

What is $E(X_{n,k})$ as a function of $n$ and $k$?

Answer 1

(Not a complete solution.)

An interesting property is this: For an edge $uv$, the distribution of $b(u)+b(v)$ conditioned on $b(u)$ is the same as the unconditional distribution (namely uniform). From this it follows that for two distinct edges $uv$, $xy$, $w(u,v)$ and $w(x,y)$ are independent even if they have one vertex in common.

Continuing the same logic, the weights are independent for a set of edges that form an acyclic subgraph. I won't use this fact, but applying it to a spanning tree gives probability $\exp(-\Omega(2^{-k}n))$ for the maximum being less than $k$ if $2^{-k}n\to \infty$.

Let $X$ be the random variable equal to the number of edges with weight $k$. Due to the pairwise independence we can easily calculate $$ \mathbb{E} X = \binom{n}{2}2^{-k+1},\quad \mathrm{Var} X = \binom{n}{2}2^{-k+1}(1-2^{-k+1}).$$ As is well known (Chebyshebv's Inequality?) the probability of a non-negative random variable being zero goes to 0 if $\mathrm{Var} X=o(\mathbb{E} X)^2$. This happens if $2^{-k}n^2\to\infty$.

Using the stronger independence noted above would allow good bounds on central moments of higher order, giving stronger results and possibly the asymptotic distribution of $X$.