0

In an attempt to colonize Mars, humanity flooded its orbit with $50$ satellites in between they created $225$ communication lines (each line exists between one pair of satellites and no two satellites have more than one line). We say that three satellites are connected if at least one of them has established communication lines with both other satellites. Determine the smallest and largest possible number of connected three satellites. Can anyone give ideas after the progress i made on ?

My progress let $P_{i,j,k}$ denotes number of connected segments in a triangle between three satellites which is connected or not, we know that if its connected 2 $\leq$ $P_{i,j,k}$ $\leq$ 3 . Similarily if not connected we get that $0$ $\leq$ $P_{i,j,k}$ $\leq$ 1 . Let number of connected satellites be $x$ then number of disconnected satellites would be $\binom{50}{3}$ - $x$ , summing these both we get $2x$ $\leq$ $\sum P_{i,j,k}$ $\leq$ $3x$ + $\binom{50}{3}$-$x$ how to find the middle part using the $225$ constraint given that what i am stuck on .

RobPratt
  • 45,619
ProblemDestroyer
  • 967

1 Answers1

3

In other words, find a graph with $50$ nodes and $225$ edges to minimize or maximize the number of triangles that contain at least two edges.

You can solve the problem via integer linear programming as follows. For $1 \le i < j \le 50$, let binary decision variable $x_{ij}$ indicate whether edge $\{i,j\}$ is selected. For $1 \le i < j < k \le 50$, let binary decision variable $y_{ijk}$ indicate whether at least two edges of triangle $\{i,j,k\}$ are selected. The problem is to minimize or maximize $$\sum_{i,j,k} y_{ijk}$$ subject to linear constraints \begin{align} \sum_{i,j} x_{ij} &= 225 \tag1 \\ 2y_{ijk} \le x_{ij} + x_{ik} + x_{jk} &\le 2y_{ijk} + 1 &&\text{for all triangles $\{i,j,k\}$} \tag2 \end{align} The maximum turns out to be $5400$. For a short proof that $5400$ is an upper bound, note that each edge appears in $50-2=48$ triangles, so $$\sum_{i,j,k} y_{ijk} \stackrel{(2)}{\le} \sum_{i,j,k} \frac{x_{ij} + x_{ik} + x_{jk}}{2} = \frac{48}{2} \sum_{i,j} x_{ij} \stackrel{(1)}{=} 24 \cdot 225 = 5400.$$

You can tighten the formulation by imposing three additional sets of constraints: \begin{align} x_{ij} + x_{ik} &\le y_{ijk} + 1 &&\text{for all triangles $\{i,j,k\}$} \tag3 \\ x_{ij} + x_{jk} &\le y_{ijk} + 1 &&\text{for all triangles $\{i,j,k\}$} \tag4 \\ x_{ik} + x_{jk} &\le y_{ijk} + 1 &&\text{for all triangles $\{i,j,k\}$} \tag5 \end{align} Note that these new constraints cut off some fractional solutions that $(2)$ would not. For example, $(x_{ij},x_{ik},x_{jk},y_{ijk})=(1,1,0,1/2)$ satisfies $(2)$ but not $(3)$.

RobPratt
  • 45,619