KPPY 94

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.

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.

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.

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.

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.