[Colloquium] Chris Godsil, Quantum walks on graphs

September 13th, 2016

FYI: Colloquium of Dept. of Mathematical Sciences.

Quantum walks on graphs.
Chris Godsil
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
2016/11/17 Thu 4:15PM-5:15PM
A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the many open problems that they have given rise to.

Ringi Kim (김린기), Unavoidable subtournaments in tournaments with large chromatic number

September 2nd, 2016
Unavoidable subtournaments in tournaments with large chromatic number
Ringi Kim (김린기)
University of Waterloo, Waterloo, Ontario, Canada
2016/9/9 Fri 4PM-5PM
For a tournament T, the chromatic number of T is the minimum number of transitive sets with union V(T). We say a set 𝓗 of tournaments is heroic if there exists c such that every tournament excluding all members of 𝓗 has chromatic number at most c. Berger et al. explicitly characterized all heroic sets of size one. In this talk, we study heroic sets of size two. This is a joint work with Maria Chudnovsky, Ilhee Kim, and Paul Seymour.

Changhyun Kwon (권창현), Mathematical Models of Transportation Systems and Networks

June 23rd, 2016

FYI: Short Course on “Mathematical Models of Transportation Systems and Networks” organized by Dept. of Industrial and Systems Engineering, KAIST. You need to bring your laptop to learn the programming in Julia.

Mathematical Models of Transportation Systems and Networks
Changhyun Kwon (권창현)
Industrial and Management Systems Engineering, University of South Florida
2016/7/5 10am-12am, 1:30pm-3:30pm
2016/7/6 10am-12am, 1:30pm-3:30pm
(Room 1501 of Bldg. E2)
This short course covers selected topics in mathematical models arising in the analysis of transportation systems and networks. We will briefly review basic topics in network optimization and then will proceed to commonly used models for logistics service planning by private companies as well as management of public vehicular infrastructure. This course will cover topics such as risk-averse routing, vehicle routing problems, network user equilibrium, road pricing and network design, location problems, and modeling drivers’ decision making processes, with applications in bike-sharing services, electric-vehicle charging, hazardous materials transportation, and congestion mitigation. This course will also introduce some computational tools available in the Julia Language.Outline (subject to change)

1. Basic Topics in Network Optimization
– Shortest Path Problem
– Minimum Cost Network Flow
– Transportation Problem
– Multi-Commodity Network Flow
– Intro to Julia and JuMP

2. Risk-Averse Routing
– Robust Shortest Path Problem
* Scenario-based
* Interval data
* Polyhedral uncertainty set
* Two multiplicative coefficients
* Julia: RobustShortestPath.jl
– Value-at-Risk
– Conditional Value-at-Risk
– Worst-case Conditional Value-at-Risk

3. Vehicle Routing Problem
– Traveling Salesman Problem
– Subtour Elimination
– Vehicle Routing Problem
– VRP with Time Windows
– Green VRP / Electric-VRP
– Energy Minimizing VRP
– Medical-Waste Collection VRP
– Bike-Balancing VRP

4. Network User Equilibrium
– System Optimum
– User Equilibrium
* Complementarity Problem
* Variational Inequality Problem
– Computation
* Frank-Wolfe Algorithm
* Julia: VariationalInequality.jl
* Julia: Complementarity.jl
* Julia: TrafficAssignment.jl
– Stochastic User Equilibrium
– Braess Paradox
– Price of Anarchy

5. Network Regulation
– Bilevel Optimization
– Road Pricing
– Network Design
– Inverse Optimization for Road Pricing
– Single-level Reformulation
– Leader-Follower Game

6. Location Problems
– Classic Location Problems
* p-median
* p-center
* set-covering
* maximal covering
* fixed-charge facility location
* two-stage problem
– Hub Location Problems
* p-hub center
* hub-covering
* p-hub median
– Lagrangian Relaxation
– Flow-Capturing Location Problem
– Flow-Refueling Location Problem
– Infrastructure Planning for Electric Vehicles

7. Generalized Bounded Rationality
– Satisficing Behavior
– Perception-Error
– Equivalence
– Comparison with Random-Utility Model
– Monte-Carlo Method
– Julia: PathDistribution.jl
– Application in Robust Network Design

Chun-Hung Liu, Packing and covering topological minors and immersions

June 10th, 2016
Packing and covering topological minors and immersions
Chun-Hung Liu
Department of Mathematics, Princeton University, Princeton, NJ, USA
2016/06/29 Wed 4PM-5PM
A set F of graphs has the Erdős-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains a set of at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdős-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980’s proved that M(H) has the Erdős-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdős-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdős-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdős-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdős-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdős-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

On the Erdős-Szekeres convex polygon problem

May 25th, 2016
On the Erdős-Szekeres convex polygon problem
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2016/05/27 4PM (Room 2411 of Bldg E6-1)
Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.