Department of


Seminar Calendar
for events the day of Wednesday, December 9, 2015.

events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    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

Wednesday, December 9, 2015

2:00 pm in 241 Altgeld Hall,Wednesday, December 9, 2015

Gromov Hyperbolicity Implies Congestion

Matt Yancey

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.

3:00 pm in 145 Altgeld Hall,Wednesday, December 9, 2015

Crystals and diagram foldings

Travis Scrimshaw (University of Minnesota)

Abstract: Crystals are combinatorial skeletons for quantum group representations and have been shown to have deep connections well beyond representation theory. We discuss two crystal models, the Littelmann path model and rigged configurations, and show that they are both reflect that natural embedding of root/weight lattices from a diagram folding.

4:00 pm in 245 Altgeld Hall,Wednesday, December 9, 2015

Factors in graphs, weighted graphs and directed graphs

Theodore Molla (University of Illinois at Urbana-Champaign)

Abstract: A factor is a subgraph that contains all of the vertices of its host graph, so a perfect matching is a factor consisting entirely of vertex disjoint edges and a Hamiltonian cycle is a factor that is a cycle. Many celebrated theorems in graph theory give sufficient conditions for the existence of a specific factor. For example, Dirac's Theorem states that if $G$ is a graph on $n$ vertices, $n \ge 3$ and the minimum degree of $G$ is at least $n/2$, then $G$ contains a Hamiltonian cycle. In this talk, we will discuss several theorems on the existence of factors in graphs, weighted graphs and directed graphs that are similar to Dirac's Theorem.