The Gossip Problem (aka realizing a temporally connected graph on $n$ vertices with as few temporal edges as possible)

• $U$ is a set of $n$ persons (vertices).
• $T = \{ t_1, t_2, \dots, t_k \}$ is an ordered sequence of $k$ calls (temporal edges | undirected, simple, proper)
  • $t_i \in T$ is an unordered pair $\{u, v\} \subseteq U$, representing a call between two distinct people
  • $T$ is referred to as a system of calls (labeling)

⏱️ Temporal Paths and Information Flow

• A temporal path (in modern terms) from aaa to bbb is a sequence of people $a = x_0, x_1, \dots, x_m = b$ together with a strictly increasing sequence of time indices

  $s_1 < s_2 < \dots < s_m$

  such that each call $t_{s_i} = \{x_{i-1}, x_i\} \in T$.

• $a\rightarrow b$ denotes that $b$ learns the information from $a$. This means that there exists a temporal path $a\rightsquigarrow b$ (strict temporal reachability)

<aside> 💡

Definition. (pooling system)

A system of calls $T$ is called pooling if for every pair $a, b \in U$ holds $a\rightsquigarrow b$

• That is, everyone eventually learns everyone else’s information.
• In modern terms, this means the graph is temporally connected (strict temporal reachability graph is complete) </aside>