KPPY 77

Jae young Yang, Youn-jin Kim, Ilkyoo Choi, Suil O, Kang-Ju Lee

KPPY 77

Jun 21, 2016 (Tues). 11am - 5:30pm at KNU

Schedule
11:00am - 11:50 Jae young Yang
POSTECH
A generalization of a theorem of Hoffman
12pm - 1:25 Lunch
1:30 - 2:20 Youn-jin Kim
Ewha
On the Erdős-Ko-Rado Theorem for $t$-intersecting families.
2:30 - 3:20 Ilkyoo Choi
KAIST
Improper colorings of graphs on surfaces
3:30 - 4:20 Suil O
Simon Fraser University, Canada
Interlacing families and the Hermitian spectral norm of digraphs
4:30 - 5:20 Kang-Ju Lee
SNU
Path-intersection matrix and applications to networks

Abstracts



Jae young Yang
A generalization of a theorem of Hoffman
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.
Youn-jin Kim
On the Erdős-Ko-Rado Theorem for $t$-intersecting families.
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.
Ilkyoo Choi
Improper colorings of graphs on surfaces
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.
Suil O
Interlacing families and the Hermitian spectral norm of digraphs
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$.
Kang-Ju Lee
Path-intersection matrix and applications to networks
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.