KPPY 77

In 1977, Hoffman gave a characterization of graphs with smallest eigenvalues at least $-2$. In this paper we generalize this result to graphs with smaller eigenvalues. For the proof, we use the concept of Hoffman graphs, as introduced by Woo and Neumaier in 1995. Our result says that if a graph with smallest eigenvalue at least $-t-1$ (where $t$ is a positive integer) satisfying some local conditions, then they are highly structured. We apply our result to graphs with smallest eigenvalue $-3$, which are cospectral to the Hamming graph $H(3,q)$, the Johnson graph $J(n, 3)$ and to the $2$-clique extensions of grids.

A family $F$ is $t$-intersecting if any two members have at least $t$ common elements. In 2014, Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. We gave a strengthening of their result by considering families generalizing $t$-intersecting families for all $t$. In this talk, I give a detailed proof and applications to other problems. This is a joint work with Dong Yeap Kang and Jaehoon Kim.

A graph is $(d_1, \ldots, d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, \ldots, V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, \ldots r\}$. Given $r$ and $d_1, \ldots, d_r$, determining if a (sparse) graph is $(d_1, \ldots, d_r)$-colorable has attracted much interest. For example, the Four Color Theorem states that all planar graphs are $4$-colorable, and therefore $(0, 0, 0, 0)$-colorable. The question is also well studied for partitioning planar graphs into three parts. For two parts, it is known that for given $d_1$ and $d_2$, there exists a planar graph that is not $(d_1, d_2)$-colorable. Therefore, it is natural to study the question for planar graphs with girth conditions. Namely, given $d_1$ and $d_2$, determine the minimum $g=g(d_1, d_2)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable. We continue the study and ask the same question for graphs that are embeddable on a fixed surface. Given integers $k, \gamma, g$ we completely characterize the smallest $k$-tuple $(d_1, \ldots, d_k)$ in lexicographical order such that each graph of girth at least $g\leq 7$ that is embeddable on a surface of Euler genus $\gamma$ is $(d_1, \ldots, d_k)$-colorable. All of our results are tight, up to a constant multiplicative factor for the degrees $d_i$ depending on $g$. In particular, we show that a graph embeddable on a surface of Euler genus $\gamma$ is $(0, 0, 0, K_1(\gamma))$-colorable and $(2, 2, K_2(\gamma))$-colorable, where $K_1(\gamma)$ and $K_2(\gamma)$ are linear functions in $\gamma$. This talk is based on results and discussions with H. Choi, F. Dross, L. Esperet, J. Jeong, M. Montassier, P. Ochem, A. Raspaud, and G. Suh.

Recently, Marcus, Spielman, and Srivastava proved the existence of infinite families of bipartite Ramanujan graphs of every degree at least $3$ by using the method of interlacing families of polynomials. In this talk, we apply their method to prove that for any connected graph $G$, there exists an orientation of $G$ such that the spectral radius of the corresponding Hermitian adjacency matrix is at most that of the universal cover of $G$.

For a network $G$, we introduce a non-singular symmetric matrix, called a {\it path-intersection matrix}, that will provide a new method for computing the ratio $k(G)/k(G/{ab})$ where $k(G)$ is the tree-number of $G$ and $G/{ab}$ is obtained from $G\cup ab$ by contracting the new edge $ab$ between two distinct nodes $a$ and $b$. The quantities $k(G)/k(G/{ab})$ appear as invariants for various networks such as effective conductance for an electrical network and an ingredient for information centrality for a social network. We will review several examples of networks where path-intersection matrices can be applied. This is a joint work with D. Kho, W. Kook, J. Lee, and J. Lee.