# KPPY 77

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

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

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.

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

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

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

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.