Skip to content

Bannai-Ito Conjecture solved

October 16, 2009

After seeing an excellent talk by Se Jeong Bang (Pusan Uni) at the last GAC conference in Oisterwijk, I’d been meaning to chase up the result which was presented there: a proof of the Bannai-Ito Conjecture. Here is the link to the preprint by Bang, Dubickas, Koolen and Moulton. This remarkable result was conjectured by Bannai and Ito in their book “Algebraic Combinatorics” (1984), and which is one of the simplest stated problems in algebraic combinatorics:

The Bannai-Ito Conjecture: Let k> 2. Then there are finitely many distance-regular graphs of valency k.

A finite, connected graph \Gamma is said to be distance-regular if, for any pair of vertices x, y and any two integers i and j the number of vertices at distance i from x and distance j from y depends only on d(x, y). Many of the really nice families of graphs are distance-regular, such as Hamming graphs, Johnson graphs, strongly regular graphs, bilinear forms graphs, incidence graphs of square designs, Grassmann graphs…

The natural precursor to the Bannai-Ito Conjecture is the 1983 result of Cameron, Praeger, Saxl and Seitz:

There are only finitely many distance-transitive graphs of a fixed valency (greater than 2).

A distance-transitive graph is a regular connected graph in which for each possible distance i, the automorphism group of the graph is transitive on pairs of vertices which are distance i apart. So necessarily, a distance-transitive graph is distance-regular, but not conversely. The Shrikhande graph is the smallest such counter-example.

The point-graphs of finite generalised polygons are distance-regular. These are the biregular bipartitie graphs which have girth twice their diameter. By a famous result of Feit and Higman, either the graph is an ordinary n-gon or the diameter is 3, 4, 6, 8 or 12. So these graphs satisfy the Bannai-Ito Conjecture. For more on the history of this problem, I urge you to read the introduction of the preprint of Bang et. al.

What I can say is that the proof of the Bannai-Ito Conjecture looks to be quite difficult and intricate, but could be understood by someone with a background in algebraic combinatorics. As far as I am aware, the paper is still under-going refereeing, and so we shall know soon whether the proof is intact and valid.

About these ads
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 38 other followers

%d bloggers like this: