# KPPY 93

Jae-baek Lee, Ilia Ponomarenko, Hyungrok Jo, Sang June Lee, Mengyue Cao

Sep 07, 2019. 11am - 5:30pm at PNU.

Schedule | ||

11:00am - 11:50 |
Jae-baek Lee Kyungpook National University | Reconfiguration of Graph Homomorphisms Problems |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Ilia Ponomarenko St. Petersburg Department of V.A. Steklov Mathematical Institute | Combinatorial bases of coherent configurations |

2:30 - 3:20 |
Hyungrok Jo University of Tsubuku | A general construction of LPS-type Ramanujan graphs |

3:30 - 4:20 |
Sang June Lee Kyung Hee University | On strong Sidon sets of integers |

4:30 - 5:20 |
Mengyue Cao Beijing Normal University | Equiangular line system and the Lemmens-Seidel conjecture |

## Abstracts

Jae-baek Lee

Reconfiguration of Graph Homomorphisms Problems

Reconfiguration of Graph Homomorphisms Problems

For a fixed graph $H$, the recolouring problem for $H$-colouring (i.e. homomorphisms to $H$) asks: given a graph $G$ and two $H$-colourings $\phi$ and $\psi$ of $G$, is it possible to transform $\phi$ into $\psi$ by changing the colour of one vertex at a time such that all intermediate mappings are $H$-colourings?
This is equivalent to asking whether there exists a sequence $f_0,\dots,f_m$
of $H$-colourings such that $f_0=\varphi$, $f_m=\psi$ and $f_i(u)f_{i+1}(v)\in E(H)$
for every $0\leq i

Ilia Ponomarenko

Combinatorial bases of coherent configurations

Combinatorial bases of coherent configurations

The combinatorial base of a coherent configuration is defined as a
subset of points that extends it to a discrete configuration. In the
framework of the Galois correspondence between coherent configurations
and permutation groups, combinatorial bases correspond to the usual
bases of the latter; in particular, the smallest size of the base of
the permutation group does not exceed the smallest size of the base of
the coherent configuration composed of
orbitals of this group. The talk is supposed to give an overview of
the known results on combinatorial bases, present new results, and
formulate several open problems.

Hyungrok Jo

A general construction of LPS-type Ramanujan graphs

A general construction of LPS-type Ramanujan graphs

A Ramanujan graph is an optimal combinatorial structure of expander graph in a sense of random walks on graphs. In general, it is difficult to find explicit constructions of Ramanujan graphs. There are only a few explicit Ramanujan graphs so far such as Cayley- type by Lubotzky-Phillips-Sarnak (LPS for short) in 1988, Morgenstern in 1994, Chiu in 1992 and Non-Cayley-type by Pizer in 1990. This work is motivated by the attempts to investigate provable cryptographic hash functions, which are called Cayley hash functions, based on such Cayley-type Ramanujan graphs.
In this talk, we present a general version of Chiu's graphs which can be seen as another case of LPS Ramanujan graphs with a preliminary of quaternion algebra for our constructions.

Sang June Lee

On strong Sidon sets of integers

On strong Sidon sets of integers

Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a

*Sidon set*if the sums $a_1+a_2$, with $a_1,a_2\in S$ and $a_1\leq a_2$, are distinct, or equivalently, if \begin{equation*} |(x+w)-(y+z)|\geq 1 \end{equation*} for every $x,y,z,w\in S$ with $x < y\leq z < w$. We define strong Sidon sets as follows: For a constant $\alpha$ with $0\leq \alpha < 1$, a set $S\subset \mathbb N$ is called an*$\alpha$-strong Sidon set*if \begin{equation*} |(x+w)-(y+z)|\geq w^\alpha \end{equation*} for every $x,y,z,w \in S$ with $x < y\leq z < w$. The motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of $\mathbb N$. In this talk, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa, Carlos Gustavo Moreira and Vojtěch Rödl. Mengyue Cao

Equiangular line system and the Lemmens-Seidel conjecture

Equiangular line system and the Lemmens-Seidel conjecture

A system of lines through the origin in $r$-dimensional Euclidean space $\mathbb{R}^r$ is called equiangular if the angle between any pair of lines is same. Let $N_{\alpha}(r)$ be the maximum number of a system of equiangular lines in $\mathbb{R}^r$ with common angle $\arccos \alpha$. In $1973$, Lemmens and Seidel conjectured $N_{\frac{1}{5}}(r)=276$ for $23\leq r\leq185$ and $N_{\frac{1}{5}}(r)=\lfloor\frac{3r-3}{2}\rfloor$ for $r\geq185$.
Recently, we were able to show the conjecture. In this talk, I will discuss the proof. The main idea is to find forbidden principal submatrices of the corresponding Seidel matrix. This is based on ongoing joint work with Jack Koolen, Yen-Chi Lin and Wei-Hsuan Yu.