KPP 40

The Hadwiger-Nelson problem asks for the minimum number of colors needed to color the real plane such that any two points at distance $ 1$ 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 $ d$-dimensional normed space. We (with Z. Füredi) have proved a lower bound of $ (1.2)^d$ and a upper bound $ c (d \ln d)5^d$ 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 $ D$ of the positive integers, we want to color all the integers such that any two integers whose Euclidean distance belongs to $ D$ are forbidden to receive the same color. One of the main goals is to characterize a prescribed distance set $ D$ that induces finite chromatic number. In this talk, we approach the problem in terms of the $ p$-adic norm. The chromatic numbers of some distance sets will be determined under $ p$-adic norm. We discuss how the $ p$-adic results can be connected to and complement some of the results in Euclidean norm. (The $ p$-adic results are joint with H. Maharaj.)

Let $\Gamma$ 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 $\Gamma$ 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 $\Gamma$ with adjacency integral eigenvalues and spectral radius $3$, as, if $\Gamma$ , is the line graph of $H$, then $|L|(H)$ has integral eigenvalues and spectral radius $5$.

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.

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).

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.