KAIST Discrete Math Seminar

In spectral graph theory one studies the eigenvalues (and spectrum) of the adjacency matrix and how they are related with combinatorial properties of the underlying graph.
In this talk, I will discuss several topics in spectral graph theory.

A web crawler is a fundamental software which iteratively downloads web pages by following links of web pages starting from a small set of initial URLs. Previously several web crawling orderings have been studied. In this talk we consider various graph search techniques including lexicographic breadth-first search, lexicographic depth-first search and maximum cardinality search as well as well-known breadth-first search and depth-first search, and then find the best web crawling ordering among them. Furthermore, we treat internal links and external links in different manners for effective crawling. For maximum cardinality search and lexicographic breadth-first search, we present linear time algorithms based on the partition refinement method. Experimental results show that maximum cardinality search is the best graph search technique for web crawlers.

An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbors receives distinct colors. The injective chromatic number, , is the minimum number of colors needed for an injective coloring. Let be the maximum average degree of G. In this paper, we show that if and . When , we show that mad(G) < \frac{36}{13}[/latex] implies [latex]\chi_i(G) \leq 5[/latex]. This is sharp; there is a subcubic graph [latex]H[/latex] such that [latex]mad(H) = \frac{36}{13}[/latex], but [latex]\chi_i(H) = 6[/latex]. This is joint work with Daniel Cranston and Gexin Yu.

Finite graphs can be viewed, in many respects, as discrete analogues
of algebraic curves. In this talk, we consider this analogy in the
context of linear equivalence of divisors on a graph. We will state a
graph-theoretic version of the Riemann-Roch theorem, and outline its
proof. Additionally, we will discuss harmonic morphisms between graphs
and connections of our results to tropical geometry. This is joint
work with Matt Baker.

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.