Suppose we have a graph $G$ on $n$ vertices $x_1 , \dots, x_n$ attached with weights of values from $1$ to $n$. We will write $\text{weight}(x_i)$ as simply $x_i$ and let $\text{diff}(G) = \min _{(x_i,x_j) \in E(G)} |x_i - x_j|$. Then, what is

$$ \max \text{diff}(G)?$$

For example, if $\text{diam}(G) = 1$ i.e. $G=K_n$ then the answer is of course $1$. Diameter, here, seems like a natural consideration, as does edge density or regularity.

Another example, if $n$ is even and $G$ is a perfect matching, then we reduce to the analysis problem of finding

$ \max \min ( |x_1 - x_2|, \dots , |x_{n-1}-x_n|)$

across all permutations $(x_1,\dots , x_n)$ of $[n]$.

Since our sample space is finite, we know that $\max \text{diff}(G) > E[\text{diff}(G)]$, where the expectation may be able to be computed exactly (as in the case that $G$ is a perfect matching).

Literature results on either of these would be nice, thank you!

Suppose we have a graph $G$ on $n$ vertices $x_1 , \dots, x_n$ attached with weights of values from $1$ to $n$. We will write $\text{weight}(x_i)$ as simply $x_i$ and let $\text{diff}(G) = \min _{(x_i,x_j) \in E(G)} |x_i - x_j|$. Then, what is

$$ \max \text{diff}(G)$$

across all permutations $(x_1,\dots , x_n)$ of $[n]$?

For example, if $\text{diam}(G) = 1$ i.e. $G=K_n$ then the answer is of course $1$. Diameter, here, seems like a natural consideration, as does edge density or regularity.

Another example, if $n$ is even and $G$ is a perfect matching, then we reduce to the analysis problem of finding

$ \max \min ( |x_1 - x_2|, \dots , |x_{n-1}-x_n|)$

across all permutations $(x_1,\dots , x_n)$ of $[n]$.

Since our sample space is finite, we know that $\max \text{diff}(G) > E[\text{diff}(G)]$, where the expectation may be able to be computed exactly (as in the case that $G$ is a perfect matching).

Literature results on either of these would be nice, thank you!