KPPY 90

The Cheeger constant of a graph is the smallest possible ratio between the size of a subgraph and the size of its boundary. It is well known that this constant must be at least $\lambda_1/2$ , where $\lambda_1$ is the smallest positive eigenvalue of the Laplacian matrix.

In this talk I will discuss the conjecture that for distance-regular graphs the Cheeger constant is at most $\lambda_1$. The conjecture has been proved for most of the known infinite families of distance-regular graphs, for distance-regular graphs of diameter 2 (the strongly regular graphs), for several classes of distance-regular graphs of diameter 3, and for most distance-regular graphs with small valency. A number of cases remain open.

This is joint work with Jacobus Koolen and Zhi Qiao.

For an association scheme $(X,S)$ and an arbitrary field $F$, we can define the adjacency algebra $FS$ of the association scheme over the field as a subalgebra of the full matrix algebra. Thus we can consider double centralizer $C^2(FS)$ of the adjacency algebra in the full matrix algebra. In general, $FS \ne C^2(FS)$, however $FS=C^2(FS)$ holds for a schurian scheme. In this talk, we will show that if $|S|\leq 3$, then $FS=C^2(FS)$ and give an example such that $FS \ne C^2(FS)$ and $|S|=4$.

We give a talk about the Abel Prize: how it came to be, how it works, who has won it, and who will win it next. This talk is a talk I accidently volunteered to give at my university, extended slightly by the inclusion of some challenging jokes.

The main goal of the talk is to establish a sufficient condition for a two-valenced association scheme to be schurian and separable. To this end, an analog of the Desargues theorem is introduced for a non-commutative geometry defined by the scheme in question. It turns out that if the geometry has enough Desarguesian configurations, then under a technical condition the scheme is schurian and separable. This result enables us to give short proofs for known statements on the schurity and separability of quasi-thin and pseudocyclic schemes. Moreover, by the same technique we prove a new result: given a prime p, any meta-thin {1,p}-scheme with thin residue isomorphic to an elementary abelian p-group of rank greater than two, is schurian and separable.

This is joint with M.Hirasaka and K.Kim.

The extremal number $ex(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $ex(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $1, 7/5, 2$, and the numbers of the form $1+(1/m), 2-(1/m),$ and $2-(2/m)$ for integers $m\geq1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.

We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that $2-(a/b)$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b\equiv\pm1$ (mod a). This includes all previously known ones, and gives infinitely many limit points $2-(1/m)$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

This is joint work with Jaehoon Kim and Hong Liu.