1
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What operation is $b(u)+b(v)$? Addition as binary numbers? Element-wise mod 2 addition? $\endgroup$ Commented May 1, 2022 at 5:25
  • $\begingroup$ Since you say "$n$ much larger than $k$" it sounds like you're looking for some sort of asymptotics. Can you say more about which regime you're interested in? The case $n\approx 2^k$ will be very different from the case $n\approx k^2$.... $\endgroup$ Commented May 1, 2022 at 14:04
  • $\begingroup$ @BrendanMcKay I have clarified what I mean by summing two binary strings. $\endgroup$ Commented May 1, 2022 at 16:13
  • $\begingroup$ @JamesMartin I believe in the relevant case $k = O(\log n)$, or even a fixed large constant independent of $n$. $\endgroup$ Commented May 1, 2022 at 16:13
  • $\begingroup$ If $k=c\log n$ for constant $c$, then the maximum is $k$ with probability bounded above 0. If $k$ is a constant, the maximum is $k$ almost surely. $\endgroup$ Commented May 2, 2022 at 5:42

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ It is not clear to me where you accounted for the fact that one needs to account for the maximum function to give the edge weights... could you please clarify? $\endgroup$ Commented May 2, 2022 at 12:55
  • $\begingroup$ @StanleyYaoXiao I'm only considering the event that the weight is k, which occurs for 2 of the $2^k$ possible values of $b(u)+b(v)$. The analysis is the same no matter which two values we are interested in. $\endgroup$ Commented May 2, 2022 at 13:10
  • $\begingroup$ I believe this gives me a good idea for what happens in the regime where $n$ is large compared to $k$. I am also interested in the reverse regime, when $n$ is small compared to $k$; see this question: mathoverflow.net/questions/421589/… $\endgroup$ Commented May 2, 2022 at 14:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.