Paul Seymour and Maria Chudnovsky, Theory of excluding induced subgraphs [KAIST CMC Annual Distinguished Lecture]

December 5th, 2014
Theory of excluding induced subgraphs
Paul Seymour Department of Mathematics, Princeton University, Princeton, NJ, USA
Maria Chudnovsky, Columbia University, New York, NY, USA
2014/12/11 Thu 10:30AM-12PM, 1:30PM-3PM
2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM
E6-1, Room 1501
This will be a series of four lectures, beginning with a general introduction to the area of induced subgraphs, and later focusing on several recent results. We will examine the structure of graphs that do not contain certain induced subgraphs, and in particular study relations between the clique number, stability number and chromatic number of these graphs. Later topics will include the strong perfect graph theorem, and recent progress on the Erdos-Hajnal conjecture, and on various conjectures of Gyárfás.

2014 KAIST CMC Discrete Math Workshop

November 23rd, 2014
December 10–12, 2014
자연과학동(E6-1), KAIST

Preregistration in kcw2014.eventbrite.com deadline: Dec. 5 (Friday)

Program (Dec.10 Wed-Room 1409)
  • 1:30-2:00 Registration
  • 2:00-2:30 Young Soo Kwon (권영수), Yeungnam University: A variation of list coloring and its properties
  • 2:40-3:10 Mitsugu Hirasaka, Pusan National University: Small topics on association schemes
  • 3:10-3:40 Coffee Break
  • 3:40-4:10 Younjin Kim (김연진),  KAIST: On Extremal Combinatorial Problems of Noga Alon
  • 4:20-4:50 Jang Soo Kim (김장수),  Sungkyunkwan University: A new q-Selberg integral, Schur functions, and Young books
  • 5:00-6:00 Discussion
  • 6:00- Dinner
Program (Dec.11 Thurs-Room 1501 & 3435)
Program (Dec.12 Fri-Room 1501)

Suil O, Spectral radius and fractional matchings in graphs

November 20th, 2014
Spectral radius and fractional matchings
in graphs
Suil O
Georgia State University
2014/12/23 Tuesday 4PM-5PM
Room 1409
A fractional matching of a graph G is a function f giving each edge a number between 0 and 1 so that \(\sum_{e \in \Gamma(v)} f(e) \le 1\) for each \(v \in V(G)\), where \(\Gamma(v)\) is the set of edges incident to v. The fractional matching number of G, written \(\alpha’_*(G)\), is the maximum of \(\sum_{e \in E(G)} f(e)\) over all fractional matchings f. Let G be an n-vertex graph with minimum degree d, and let \(\lambda_1(G)\) be the largest eigenvalue of G. In this talk, we prove that if k is a positive integer and \(\lambda_1(G) < d\sqrt{1+\frac{2k}{n-k}}\), then \(\alpha'_*(G) > \frac{n-k}{2}\).

[CS Colloquium] Sungjin Im, Competitive Scheduling from Competitive Equilibria

November 19th, 2014

FYI (CS Colloquium)

Competitive Scheduling from Competitive Equilibria
Sungjin Im
Department of Electrical Engineering and Computer Science, UC Merced, CA, USA
2014/12/08 Mon 4PM-5:30PM
Scheduling jobs is a fundamental problem that arises in numerous forms and in various situations. In this talk, we introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates at which a scheduler can process jobs are subject to arbitrary packing constraints. The PSP framework captures a variety of scheduling problems, including the classical problems of heterogeneous machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling. We design non-clairvoyant online algorithms for PSP and its special cases, meaning that they make scheduling decisions without knowing the future jobs, or even outstanding jobs sizes until their completion. Interestingly, our algorithms are inspired by ideas developed in game theory, which at first sight seems to have no connection to online scheduling.

Jon Lee, Matroid Optimization

November 18th, 2014
Matroid Optimization
Jon Lee
University of Michigan, Ann Arbor, USA.
2014/12/04 *Thursday* 4PM-5PM
Room 1409
Matroids can be seen an an abstraction for understanding the essence of algorithms for some classical graph problems: (i) optimum-weight spanning tree, and (ii) optimum-weight assignment. We will see some recent results showing how matroids have further natural roles in various combinatorial-optimization problems where some local-search and linear-programming-based algorithms find provably-good approximations. In particular, we will look at: (iii) constrained submodular-function maximization, (iv) the well-known matroid matching problem, and (v) various nonlinear-objective matroid-intersection problems.