Department of

November 2015 December 2015 January 2016 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 1 2 3 4 5 1 2 8 9 10 11 12 13 14 6 7 8 9 10 11 12 3 4 5 6 7 8 9 15 16 17 18 19 20 21 13 14 15 16 17 18 19 10 11 12 13 14 15 16 22 23 24 25 26 27 28 20 21 22 23 24 25 26 17 18 19 20 21 22 23 29 30 27 28 29 30 31 24 25 26 27 28 29 30 31

Wednesday, December 9, 2015

**Abstract:** In this talk we will explore routing networks and conditions that would cause congestion in those networks. For a fixed graph $G$ with vertices $u,v$, let $P_{u,v}$ denote the set of paths from $u$ to $v$ of minimum length. As shorthand, let $n = \|V(G)\|$. Let $P_{u,v}(w) = \{ P \in P_{u,v} : w \in P\}$. We define the *demand* at a vertex $w$ to be $ \sum_{u,v} \|P_{u,v}(w)\| / \|P_{u,v}\|, $ and denote it by $D(w)$. In most real-world networks, the average and maximum value of $d(u,v)$ for arbitrary vertices $u, v$ is around $c \log(n)$, so the average value of demand is around $c n \log(n)$. If $G$ is drawn from some probabilistic model $M$, then we say that $M$ has *congestion* if with high probability $0 < n^{-2} \max_{w \in G} D(w) $ (informally, congestion is when some vertex has to deal with a constant proportion of all traffic flowing through the network). The Autonomous System Network (i.e. the commercial interactions that run the Internet) is well-known to be congested. In a ground breaking project, it has been shown that the ASN has an embedding into a hyperbolic plane with small distortion. A question of intense study recently has been whether or not hyperbolicity could be used to imply the existence of congestion. Gromov defined when a group is hyperbolic based on a property that the group's Cayley graph does or does not satisfy. Specifically, a graph $G$ is $\delta$-hyperbolic if for every four vertices in $G$ combined with any ordering $a_1, a_2, a_3, a_4$ satisfy $ \max \{d(a_1, a_2) + d(a_3, a_4) , d(a_1, a_3) + d(a_2, a_4) \} + \delta \geq d(a_1, a_4) + d(a_2, a_3) . $ A group is hyperbolic if its Cayley graph is $\delta$-hyperbolic for some finite $\delta$. Using this condition as our discrete analogue of hyperbolicity, we provide the first rigorous results relating hyperbolicity to congestion.