94th KPPY Combinatorics Workshop -- Nov 09, 2019

Date: Nov 09, 2019
Time: 11am - 5:30pm
Location: POSTECH
Math Building, Room 404

Schedule
11:00 - 11:50 Jieun Kwon
POSTECH
Classification of weighted posets and digraphs
12:00 Lunch  
1:30 - 2:20 Hayoung Choi
SNU
Comparing large-scale graphs based on quantum probability theory
2:30 - 3:20 Seunghun Lee
KAIST
Near-$(3k-4)$-Leray property of the complex of graphs with matching number less than $k$
3:40 - 4:30 Ying Ying Tan
Anhui Jianzhu University
A spectral characterization of the $s$-clique extension of the triangular graphs
4:40 - 5:30 Jack Koolen
University of Science and Technology of China
Clique and co-clique spectum bounds for strongly regular graphs
6:00 - 8:00 Banquet  
Program

Abstracts

Jieun Kwon
Classification of weighted posets and digraphs
Recently T. Etzion, M. Firer and R. Machado introduced metrics on $F_2^n$ based on directed graphs on $n$ vertices and developed some basic coding theory on directed graph metric spaces. In this talk, we classify weighted posets and directed graphs which admit the extended Hamming code of length $8$ or $16$ to be a $2$-perfect code.
Hayoung Choi
Comparing large-scale graphs based on quantum probability theory
Graph is one of the most common representations of complex data and plays a crucial role in various research areas and many practical applications. Recently many different approaches to find similarity between two graphs are proposed for efficient algorithms. However, these methods are not scalable to large-scale graphs containing millions of edges, which are common in today's applications. As a result, effective and scalable methods for large-scale graphs comparison are urgently needed.

In this talk, a new distance to compare two large-scale graphs based on the theory of quantum probability is introduced. Our proposed distance between two graphs is defined as the distance between the corresponding moment matri- ces of their spectral distributions. An explicit form for the spectral distribution of the corresponding adjacency matrix of a graph is established. It is shown that the spectral distributions of their adjacency matrices in a vector state includes information not only about their eigenvalues, but also about the corresponding eigenvectors. Also, such distance includes enough information of the structure of a graph. Moreover, we prove that such distance is graph invariant and sub- structure invariant. Various examples are given, and the proposed distances between graphs with few vertices are shown. Computational results for real large-scale graphs and random graphs show that its accuracy is better than any existing methods and time cost is extensively cheap.
Seunghun Lee
Near-$(3k-4)$-Leray property of the complex of graphs with matching number less than $k$
Let ${NM}_k(H)$ be the complex consisting of subgraphs of $H$ with matching number less than $k$, that is, ${NM}_k(H):=\{G \subseteq H \colon \nu(G)< k \}$. We show that ${NM}_k(H)$ is near-$(3k-4)$-Leray, that is, for every nonempty face $\sigma \in {NM}_k(H)$, we have $\tilde{H}_i(lk_{{NM}_k(H)}(\sigma))=0$ for every $i \geq 3k-4$.

As a corollary, via Holmsen's topological generalization of the colorful Caratheodory theorem, we show that there exists a rainbow matching of size $k$ for given edge sets $E_1, \dots, E_{3k-2}$, when the condition $\nu(E_i \cup E_j)\geq k$ is satisfied for every $i\ne j$.

The proof follows and extends the previous argument by Linusson, Shareshian, and Welker, and uses the discrete Morse theory and the Gallai-Edmonds decomposition.

This is joint work with Andreas Holmsen.
Ying Ying Tan
A spectral characterization of the $s$-clique extension of the triangular graphs
A regular graph is co-edge regular if there exists a constant $\mu$ such that any two distinct and non-adjacent vertices have exactly $\mu$ common neighbors. In this talk, we show that for integers $s\ge 2$ and $n\ge 1$, any co-edge-regular graph which is cospectral with the $s$-clique extension of the triangular graph $T(n)$ is exactly the $s$-clique extension of the triangular graph $T(n)$, if $n$ is large enough. This is a follow-up work of Hayat, Koolen and Riaz (2019).

This is a joint work with Jack H. Koolen and Zheng-jiang Xia.
Jack Koolen
Clique and co-clique spectum bounds for strongly regular graphs
We look at the bounds on the eigenvalues of some nicely regular graphs in terms of the clique numbers and independence numbers and use this to show that strongly regular graphs with certain parameters cannot exist.