Dept. of Mathematical Sciences, KAIST, Korea.

^{s}is 2

^{s+1}for s>2. We also consider the largest power of 2 in the number of even and odd involutions.

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

A combinatorial approach to the power of 2 in the number of involutions

Jang Soo Kim (김장수)

Dept. of Mathematical Sciences, KAIST, Korea.

Dept. of Mathematical Sciences, KAIST, Korea.

2008/12/11 Thu, 5:30PM-6:30PM

We prove combinatorially that the largest power of 2 in the number of involutions of length n is equal to [n/2]-2[n/4] +[(n+1)/4]. We show that the smallest period of the sequence of odd factors in the number of involutions modulo 2^{s} is 2^{s+1} for s>2. We also consider the largest power of 2 in the number of even and odd involutions.

Turán type problems forbidding complete graphs and complete multipartite graphs together

Yoomi Rho (노유미)

Dept. of Mathematics, Univ. of Incheon, Incheon, Korea.

Dept. of Mathematics, Univ. of Incheon, Incheon, Korea.

2008/11/28 Fri, 4PM-5PM

A Turán type problem looks for the maximum number of edges of a graph of a given order that does not contain given forms of graphs as subgraphs. These given forms of subgraphs are called the *forbidden graphs* of the problem. This problem also looks for the forms of graphs which have the maximum number of edges. This line of research is started by Turán who solved the problem forbidding complete graphs in 1941. Problems forbidding complete bipartite graphs or even cycles have been considered. Also there are asymptotic results on problems forbidding complete multipartite graphs. In 1994, Brualdi and Mellendorf raised the following problem which forbids a complete graph and a complete bipartite graph together.

Let t and n be positive integers with n≥t≥2. Determine the maximum number of edges of a graph of order n that contains neither K

_{t}nor K_{t,t}as a subgraph.

They also solved this problem when n=2t. Obviously when n<2t, the problem reduces to Turán's problem which forbids only K_{t}. We solve the problem when n=2t+1. We raise a problem which forbids K_{t} and K_{t,n-t} together and a problem which forbids K_{t} and K_{t,t,t} together.

Approximability of a batch consolidation problem

Sung-Pil Hong (홍성필)

Dept. of Industrial Engineering, Seoul National University, Seoul, Korea.

Dept. of Industrial Engineering, Seoul National University, Seoul, Korea.

2008/11/14 Fri, 4PM-5PM

We consider a problem of minimizing the number of batches of a fixed capacity processing the orders of various sizes on a finite set of items. This *batch consolidation problem* is motivated by the batch production system typical in raw material industries in which multiple items can be processed in the same batch in case they share sufficiently close production parameters. We focuse on the special case in which up to 2 items can be processed in a single batch. The problem is NP-hard and can not be approximated within 1.00142 of the optimum under the premise, P ≠ NP as can be shown by a polynomial reduction from the vertex cover problem with bounded degree. However, the problem admits a 3/2 -approximation. The idea is to decompose the orders of items so that a maximum matching in the graph on the vertices of the decomposed orders provides a well-consolidated batch set.

Price of Anarchy in Transportation Networks

Hawoong Jeong (정하웅)

Dept. of Physics, KAIST, Daejeon, Korea.

Dept. of Physics, KAIST, Daejeon, Korea.

2008/10/30 Thu, 4PM-5PM

Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most beneficial state to the society as a whole. Instead, strategies form Nash equilibria, which are, in general, socially suboptimal. Society, therefore, has to pay a price of anarchy for the lack of coordination among its members, which is often difficult to quantify in engineering, economics and policymaking. Here, we report on an assessment of this price of anarchy by analyzing the road networks of Boston, New York, and London as well as complex model networks, where one’s travel time serves as the relevant cost to be minimized. Our simulation shows that uncoordinated drivers possibly spend up to 30% more time than they would in socially optimal traffic, which leaves substantial room for improvement. Counterintuitively, simply blocking certain streets can partially improve the traffic condition to a measurable extent based on our result.

One-sentence summaries: Traffic in transportation networks – often substantially suboptimal due to a lack of coordination among users – can be guided to the social optimum without directly controlling individual behavior by adjusting the underlying network structure appropriately.

Points surrounding the origin

Andreas Holmsen

Div. of Computer Science, KAIST, Daejeon, Korea.

Div. of Computer Science, KAIST, Daejeon, Korea.

2008/10/09 Thu, 3PM-4PM

Many problems in discrete and computational geometry can be reduced to combinatorial questions concerning systems of segments or triangles in the plane. In spite of what (little) we can say about these planar questions, much less is known in higher dimensions. In this talk we will survey some of these questions and classical results, and present the following theorem: Let d>2 and n>d+1 and P a set of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any point p in P, the simplex spanned by Q and p does not contain the origin in its interior. This answers a question by R.Strausz, and along the way we strengthen the Colored Helly and Caratheodory theorems, due to L. Lovász and I. Bárány, respectively.

Joint work with János Pach and Helge Tverberg.