Consider a connected graph of N nodes. Assign randomly to each node a distinct number from 1 to N. For each node consider the maximum adjacent value or itself if all adjacent values are smaller. Define the set that contains these distinct values. Can you deliver an upper bound for the expected value of the cardinality of this set like c*N for any connected graph of N nodes?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What are the connectivity assumptions of the graph? If I understand you correctly for a complete (fully connected) graph the cardinality of this set is equal to 1. $\endgroup$– WaldemarCommented Dec 5, 2013 at 16:02
-
$\begingroup$ For the complete graph no matter how you label the nodes (N! cases) indeed the set contains exactly one value and the expected value is 1 (the worst case). I am looking for an upper bound. For example when N=2 this is 1 and for N=3 maximum expected value that can be obtained is 5/3. $\endgroup$– heartworkCommented Dec 5, 2013 at 16:10
-
$\begingroup$ An undirected graph. $\endgroup$– heartworkCommented Dec 5, 2013 at 16:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
To obtain some linear bound you need just to assume that each vertex has degree at least one.
Say that the vertex contains tthe number $a_i$, and its maximum is $b_i$. The probability that $b_i\leq N/2$ is less than $1/4$ (in fact, it is less that $1/2^{d+1}$ where $d$ is the degree of the $i$th vertex). Thus the expected number of vertices with $b_i\leq N/2$ is less than $N/4$, and, a fortiori, the expected number of such values is less than $N/4$. Therefore, the expected number of distinct values is at most $3N/4$.
(We need to be a bit more careful with odd $N$, but at least the asymptotics is clear.)
Surely this estimate is quite rough.
-
$\begingroup$ Please can you be more specific - I am not convinced that probability of b at most N/2 is less than 1/4 - in some cases b equals a. (I am sure that probability of a at most N/2 is less than 1/2 - why should be true that probability in case of degree d) Thanks $\endgroup$ Commented Dec 5, 2013 at 18:56
-
$\begingroup$ Well, for $b_i\leq N/2$ we need the value of $a_i$ and the value at each neighbor of this vertex be at most $N/2$; if there is one neighbor (and $N$ is even) this gives the probability $\frac{(N/2)(N/2-1)}{N(N-1)}<1/4$. For the larger degree the formula is analogous. $\endgroup$ Commented Dec 5, 2013 at 19:00
-
$\begingroup$ It's easier to think about this in the equivalent model of giving each vertex a uniform random real in $[0,1]$. $\endgroup$ Commented Dec 6, 2013 at 1:59
-
$\begingroup$ How can you prove this is less than 3N/4 for all integers N anyway ? $\endgroup$ Commented Dec 6, 2013 at 6:32
-
$\begingroup$ We know that the expected number of values of $b_i$ which are less than $N/2$ does not exceed $N/4$. Surely, the expected number of the pthers is at most $N/2$. $\endgroup$ Commented Dec 6, 2013 at 7:04