2024 Combinatorics Workshop

Towards a classification of 1-homogeneous graphs with positive intersection number a1

28 Aug 2024, 17:00

30m

107 (Bldg. S1-6 (자연대6호관))

Contributed Talk

Speaker

Jae-Ho Lee (University of North Florida & POSTECH)

Description

Let $\mathrm{\Gamma }$ be a graph with diameter at least two. Then $\mathrm{\Gamma }$ is said to be $1$-homogeneous (in the sense of Nomura) whenever for every pair of adjacent vertices $x$ and $y$ in $\mathrm{\Gamma }$, the distance partition of the vertex set of $\mathrm{\Gamma }$ with respect to both $x$ and $y$ is equitable, and the parameters corresponding to equitable partitions are independent of the choice of $x$ and $y$. Assume $\mathrm{\Gamma }$ is $1$-homogeneous distance-regular with intersection number $a_1>0$ and diameter $D⩾5$. Define $b=b_1/({\theta }_1+1)$, where $b_1$ is the intersection number and ${\theta }_1$ is the second largest eigenvalue of $\mathrm{\Gamma }$. In this talk, we show that if intersection number $c_2⩾2$, then $b⩾1$ and one of the following (i)--(vi) holds: (i) $\mathrm{\Gamma }$ is a regular near $2D$-gon, (ii) $\mathrm{\Gamma }$ is a Johnson graph $J(2D,D)$, (iii) $\mathrm{\Gamma }$ is a halved $\ell$-cube where $\ell \in \{2D,2D+1\}$, (iv) $\mathrm{\Gamma }$ is a folded Johnson graph $\overline{J}(4D,2D)$, (v) $\mathrm{\Gamma }$ is a folded halved $(4D)$-cube, (vi) the valency of $\mathrm{\Gamma }$ is bounded by a function of $b$. Moreover, we characterize $1$-homogeneous graphs with classical parameters and $a_1>0$, as well as tight distance-regular graphs. This is a joint work with J. Koolen, M. Abdullah, B. Gebremichel.