KPPY 93

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.

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.

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.

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.