# Mathematics of Large Networks - Open Problems

- **(Benjamin Piazza)** Given $N$ unlabeled points (nodes of a graph $G$) fixed in a $d$-dimensional Euclidean space, s.t., an $N$ by $N$ adjacency matrix $A$ is associated with the wiring of the points. Then there are $N!$ ways of labeling the nodes. What is (or are) the labeling(s) which minimize the total euclidian distance between the nodes $L = \sum _{i<j}d_{ij}$.
- Endre Csóka: Use a minimum-weight perfect matching algorithm with some modification, I told the details to Benjamin.

- **(Tejas Iyer)** Suppose we are given a squid games/ hunger games scenario where individuals fight to the death. Or, less violently, companies merge until a monopoly is formed. We are given $N$ individuals with i.i.d. random weights $W_1, \ldots, W_N$. We are also given a function $f: \mathbb{R}^2 \rightarrow [0, \infty)$. Across each ordered pair of individuals $(i,j)$ there is an exponential clock with rate $f(W_i, W_j)$. When this clock rings, the individual $j$ is removed from the system; and this procedure is continued until there is only one individual left. What is the distribution of the weight of the final individual? Any other (possibly more tractable) variants of this problem would also be interesting.
-

- **(David Gamarnik)** Splitting a sparse ER-graph with the minimum amount of edges

Minimum Bisection Problem (MBS) is the problem of splitting the nodes of an $n$ node graph into two equal parts (assume $n$ even) to minimize the number of crossed edges. Let $MBS(G)$ be the value of MINBS on a graph $G$. Let $\mathbb{G}(n,d/n)$ be a sparse random graph.

Conjecture: The sequence
\begin{align*}
{\mathbb{E}[MBS(\mathbb{G}(n,d/n))]\over n}
\end{align*}
converges to some limit as $n\to\infty$. Note that the value is trivially upper bounded by the constant $d/2$ -- the total number of edges normalized by $n$. The limit is zero when $d<1$ since when there is no giant component, the small components can be put into the same parts thus no edges are crossed.
minimize {\cblue $\alpha\: \exists b, m$} satisfying)

\medskip

\noindent
\begin{center}
{\cblue $T = \big\{(x, y) \bigwhere 0 \le x;\ 0 \le y;\ x + y \le 1 \big\}$}; \hspace*{2mm} {\cblue $b : [0, 1] \rightarrow \R$}; \hspace*{2mm} {\cblue $m : T \rightarrow \R$}

\medskip
{\cblue $b(0) = b(1) = m(0, 0) = m(0, 1) = m(1, 0) = 0$}

\medskip
{\cblue $b$} and {\cblue $m(x, y) - b(x)$} and {\cblue $m(x, y) - b(y)$} are all concave functions

\medskip
{\cblue $\frac{4}{3} \cdot b(\alpha) > m(\alpha, \alpha)$}.
\end{center}
Some reference for the actual limit values, based on non-rigorous replica-symmetry-breaking computations from the theory of spin glasses, can be found in here https://iopscience.iop.org/article/10.1088/1742-5468/2010/02/P02020/meta?casa_token=BkZlqh8qlfcAAAAA:GYpqjtgrzFJuZtuOVXOJ4J74kN73cBd54Fpe1XStwqpBfxa2IGtXAotCZTOckWJ1bjlxCxuYwTc

Here though we are justing asking to prove that the limit exists, and not necessarily computing the actual value. Some relevant references:

https://projecteuclid.org/journals/electronic-communications-in-probability/volume-23/issue-none/Convergence-of-maximum-bisection-ratio-of-sparse-random-graphs/10.1214/18-ECP164.full

https://web.stanford.edu/~bayati/papers/interpolation.pdf

- **(Gábor Pete) Mixing time of random walk on dynamic random graphs.** **(1)** Take your favourite critical random graph. For me, Bernoulli$(1/2)$ bond percolation in the $n\times n$ box of the square lattice. **(2)** Consider a natural stationary dynamics. In the percolation example, let each edge have a rate 1 Poisson clock resampling its status. **(3)** Take random walk on the open edges. Say, continuous time random walk, at steps given by rate $\sigma$ Poisson clocks on the edges. Let's take infinite speed now, $\sigma=\infty$, so that we get rid of hard questions such as mixing time of RW on fractal-like graphs. That is, the particle is always distributed within its current cluster according to the stationary measure restricted to the cluster, which is just uniform now (because we took CTRW). **Annealed question:** How much time is needed for the particle to be approximately uniform in the box? Say, in total variation distance.
- I (still Gábor) expect fast mixing (time $O(1)$ or $O(\log n)$), due to the fact that even though we do not see giant clusters (in volume), the macroscopic structure of the clusters is changing very fast, by noise sensitivity and exceptional times arriving quickly, see [Garban-Pete-Schramm (Acta Math 2010)](https://arxiv.org/abs/0803.3750) and [Hammond-Mossel-Pete (Elect J Probab 2012)](https://arxiv.org/abs/1111.6618). References about RW on dynamical percolation, but with non-critical percolation and finite $\sigma$, are [Peres-Stauffer-Steif (PTRF 2015)](https://arxiv.org/abs/1308.6193) and [Peres-Sousi-Steif (PTRF 2020)](https://arxiv.org/abs/1707.07632). The $\sigma=\infty$ question came up in a conversation with Balázs Ráth and Jeff Steif in 2017.
- A lower bound $\Omega(1)$ is easy (still by Gábor): typically, the cluster of the origin (where the RW particle starts) is small at time 0, so typically it takes time $\Omega(1)$ for the cluster to change at all.
- I (still Gábor) think there is also a general ideological question here: what should the definition of a **temporal expander** be? I think the above HMP EJP'12 paper might be relevant here.

- **(Endre Csóka)** Minimize $\alpha$ such that $\exists b, m$ satisfying
1. $\ \ \ m : T \rightarrow \mathbb{R}\,\,$ where $\ T = \big\{(x, y) \ \big|\ 0 \le x;\ 0 \le y;\ x + y \le 1 \big\}$
2. $\ \ \ b : [0, 1] \rightarrow \mathbb{R}$
3. $\ \ \ b(0) = b(1) = m(0, 0) = m(0, 1) = m(1, 0) = 0$
4. $\ \ \ b$ and $m(x, y) - b(x)$ and $m(x, y) - b(y)$ are all concave functions
5. $\ \ \ \frac{4}{3} \cdot b(\alpha) > m(\alpha, \alpha)$.

Solving it would help understanding random graphs and their phase transitions, see: Lemma 4.5. in https://arxiv.org/pdf/1811.09560.pdf or ask me for more about the background. $\alpha$ should be around 0.45.
- Let me know if you are thinking about trying to solve it, or you know somebody who is a better fit for solving it. (Endre)