FYI: Colloquium of Dept. of Mathematical Sciences.

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

FYI: Colloquium of Dept. of Mathematical Sciences.

Quantum walks on graphs.

Chris Godsil

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

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.

Unavoidable subtournaments in tournaments with large chromatic number

Ringi Kim (김린기)

University of Waterloo, Waterloo, Ontario, Canada

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.

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

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)

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

Packing and covering topological minors and immersions

Chun-Hung Liu

Department of Mathematics, Princeton University, Princeton, NJ, USA

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

Andreas Holmsen

Department of Mathematical Sciences, KAIST

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.