2
$\begingroup$

Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $V_2$ all have degree $n-1$ and connected to $n-1$ vertices in $V_1$.

I have integers $2^m<a_1,\dots,a_{\frac{n(n-1)}2}<2^{m+1}$ where $m\in\Bbb N$ assigned to each vertex in $V_1$. At every $i\in\Big\{1,\dots,\frac{n(n-1)}2\Big\}$ denote $r(i)$ and $s(i)$ to be two vertices in $V_2$ that are connected to $a_i$. I want to have $b_1,\dots,b_n\in\Bbb R$ assigned to vertices in $V_2$ such that $$J=\sum_{i=1}^{\frac{n(n-1)}2}(a_i-(b_{r(i)}+b_{s(i)}))^2$$ is minimized.

(1) Can this always be done in time $(nm)^c$ for some fixed $c\in\Bbb R$?

(2) What is the distribution of $J$ among all assignments of $a_i$? For instance can $J\leq\frac{n(n-1)}2m^\alpha$ and $\max_{i\in\{1,\dots,\frac{n(n-1)}2\}}(a_i-(b_{r(i)}+b_{s(i)}))^2\leq m^\alpha$ where $\alpha\in\Bbb R$ is fixed be possible with probability $1-\frac1{nm}$ where $a_i$'s are picked uniformly independently?

Improve this question
$\endgroup$
7
  • $\begingroup$ It's just a positive-definite quadratic form. $O(n^3)$ by naive linear algebra. $\endgroup$
    – Brendan McKay
    Commented Feb 22, 2016 at 10:03
  • $\begingroup$ @BrendanMcKay Can $J$ be as small as $m^\alpha$ for some fixed $\alpha>0$ for $1-1/n$ of the assignments? Also could you please explain the positive definite quadratic form part? $\endgroup$
    – user76479
    Commented Feb 22, 2016 at 10:09
  • $\begingroup$ Can two vertices in $V_1$ have the same neighbours in $V_2$? If not, an exact analytic solution is possible. $\endgroup$
    – Brendan McKay
    Commented Feb 22, 2016 at 12:53
  • $\begingroup$ @BrendanMcKay Let $i,j$ be vertices in $V_1$. We cannot have both neighbors $r(i),s(i)$ of $i$ same as both neighbors $r(j),s(j)$ of $j$. However we can have one of $r(i)$ or $s(i)$ agreeing with one of $r(j)$ or $s(j)$ (that is only one neighbor may agree). $\endgroup$
    – user76479
    Commented Feb 22, 2016 at 17:52
  • $\begingroup$ Fine, so basically you have a complete graph with a $b$-variable associated with each vertex and an $a$-variable associated with each edge. I'll post a solution (or description of how to find one). $\endgroup$
    – Brendan McKay
    Commented Feb 22, 2016 at 22:40

1 Answer 1

Reset to default
2
$\begingroup$

I'm going to change notation a little, using $a_{jk}$ instead of $a_i$ for the vertex $i$ with $r(i)=j$ and $s(i)=k$, and $x_i$ instead of $b_i$. The objective function is $$ J(\boldsymbol{x}) = \sum_{1\le j\lt k\le n} (a_{jk}-(x_j+x_k))^2. $$ Minimizing a quadratic form is standard stuff, see for example this description (Prop. 12.2). Write the expression in the standard form $$J(\boldsymbol{x}) = \tfrac12 \boldsymbol{x}^T A\boldsymbol{x} - \boldsymbol{b}^T\boldsymbol{x} + c$$ with $A$ symmetric. You will find that the matrix $A$ has diagonal entries $2(n-1)$ and off-diagonal entries $2$, so it is positive-definite and its inverse has the same form (constant diagonal and constant off-diagonal). The minimum value then occurs with $\boldsymbol{x}=A^{-1}\boldsymbol{b}$ and has value $$-\tfrac12\boldsymbol{b}^TA^{-1}\boldsymbol{b} + c.$$ Given the simple form of $A^{-1}$ you can write this as a sum over entries of $\boldsymbol{b}$.

I'll let you take it from there.

Improve this answer
$\endgroup$
7
  • $\begingroup$ It is clear this is the solution for 1. My query also was more about error value $J$ and statistics of $J$. $\endgroup$
    – user76479
    Commented Feb 22, 2016 at 23:04
  • $\begingroup$ I'd start by deriving the explicit value of the minimum. It's a quadratic polynomial in the parameters, probably quite simple and symmetric. Then it should be clear how to proceed from there. $\endgroup$
    – Brendan McKay
    Commented Feb 22, 2016 at 23:10
  • $\begingroup$ What is $\boldsymbol b$? $\endgroup$
    – user76479
    Commented Feb 23, 2016 at 5:45
  • $\begingroup$ $\boldsymbol{b}$ is the coefficient in the second term of the standard form. That is, the vector that makes $\sum_{j\gt k} -2a_{jk}(x_j+x_k) = -\boldsymbol{b}^T\boldsymbol{x}$. $\endgroup$
    – Brendan McKay
    Commented Feb 23, 2016 at 10:55
  • $\begingroup$ So in essence it is very rare that $J<m^\alpha$ holds asymptotically as $n$ increases for any fixed $\alpha>0$? even impossible? $\endgroup$
    – user76479
    Commented Feb 23, 2016 at 10:59

You must log in to answer this question.