40th KPP Combinatorics Workshop - June 21 2010

secttitle: | June 21 (monday), 2010 |

Time: | 11am - 5:30pm ( dinner from 6pm ) |

Location: | College of Natural Sciences, Building 1, Room 218 |

Schedule | ||

11:00 | Jeong Hyun Kang University of West Georgia, USA | Geometry and Number Theory in Distance Graph Problems |

12:00 | Lunch | |

1:30 | Tae Young Jeong Postech University, Pohang | Classification of integral line graphs with spectral radius three |

2:30 | Hemanshu Kaul Illinois Institute of Technology, USA | Guarding Art Galleries using Graph Coloring |

3:30 | Yasuhisa Saito Pusan National University, Pusan | Global asymptotic stability for predator-prey systems with prey receiving time-variation of the environment |

4:30 | Sang Il Oum KAIST, Daejeon | Well-quasi-ordering conjecture for pivot-minors |

6:00 | Dinner |

## Abstracts

Jeong Hyun Kang

Geometry and Number Theory in Distance Graph Problems

Geometry and Number Theory in Distance Graph Problems

Hadwiger-Nelson problem asks for the minimum number of colors needed to color the real plane such that any two points at distance are forbidden to receive the same color. The best known lower and upper bounds of are 4 and 7, with no improvement in the last 50 years. This problem can be generalized to any -dimensional normed space. We (with Z. Füredi) have proved a lower bound of and a upper bound
on this chromatic number. In this talk, we will show the lower bound using an algebraic result Frankl-Wilson inequality.

This problem has also been studied from a number theoretic point-of-view. For a given subset of the positive integers, we want to color all the integers such that any two integers whose Euclidean distance belongs to are forbidden to receive the same color. One of the main goals is to characterize a prescribed distance set that induces finite chromatic number. In this talk, we approach the problem in terms of the -adic norm. The chromatic numbers of some distance sets will be determined under -adic norm. We discuss how the -adic results can be connected to and complement some of the results in Euclidean norm. (The -adic results are joint with H. Maharaj.)

Tae Young Jeong

Classification of integral line graphs with spectral radius three

Classification of integral line graphs with spectral radius three

Let be a graph with adjacency matrix A and degree matrix D. Then the signless Laplace matrix |L| is defined as |L|=D+A. In this talk, we classify all graphs which signless Laplace matrix has only integral eigenvalues and the spectral radius of |L| is at most 5. As a consequence we find all line graphs with adjacency integral eigenvalues and spectral radius 3, as, if , is the line graph of H, then |L|(H) has integral eigenvalues and spectral radius 5.

Hemanshu Kaul

Guarding Art Galleries using Graph Coloring

Guarding Art Galleries using Graph Coloring

The original art gallery problem (V.Klee, 1973) asked for the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon (Art Gallery). Chvatal (1975) proved that n/3 guards are always sufficient. Since then many variations of this problem have been studied. We will give a short introduction to many such problems and open questions therein. In particular, we will focus on some progress in Orthogonal Art gallery with holes (a polygon with visibility obstructions whose all edges are either horizontal or vertical). We will illustrate how graph coloring is a major tool for finding such guard assignments.

Yasuhisa Saito

Global asymptotic stability for predator-prey systems with prey receiving time-variation of the environment

Global asymptotic stability for predator-prey systems with prey receiving time-variation of the environment

A predator-prey model with prey receiving time-variation of the environment
is considered. Such a system is shown to have a unique interior equilibrium
that is globally asymptotically stable if the time-variation is bounded and
weakly integrally positive. In particular, the result tells that the equilibrium point
can be stabilized even by nonnegative functions that make the limiting
system structurally unstable. The method used to obtain the result is an
analysis of asymptotic behavior of the solutions of an equivalent system to
the predator-prey model. This is a joint work with Prof. Jitsuro Sugie (Shimane
University, Japan) and Prof. Meng Fan (Northeast Normal University, P R China).

Sang Il Oum

Well-quasi-ordering conjecture for pivot-minors

Well-quasi-ordering conjecture for pivot-minors

The graph minor theorem of Robertson and Seymour, one of the deepest
theorems in graph theory, states that every infinite set of graphs
contains a pair G, H of graphs such that G is isomorphic to a minor of
H. I will talk about a similar conjecture on pivot-minors of graphs.
Surprisingly, this conjecture, if true, would imply the graph minor
theorem as well as the recently announced theorem by Geelen, Gerards,
and Whittle on the well-quasi-ordering of binary matroids.