### 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 |

## Abstracts

Jieun Kwon

Classification of weighted posets and digraphs

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

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.

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$

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.

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 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.

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

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.