Q-полиномиальный граф с массивом пересечений {60, 45, 8; 1, 12, 50} не существует

1Институт математики и механики им. Н.Н. Красовского, Екатеринбург, Россия ,

Alexander A. Makhnev1, Viktoriya V. Bitkina2, Alina K. Gutnova3 1N.N. Krasovskii Institute of Mathematics and Mechanics, Yekaterinburg, Russia ,

Рассмотрим вполне регулярный граф Γ диаметра d , в котором для подходящей вершины a пара (Γ d ( a ) , Γ d -1 ( a )) является 2-схемой. Ранее было доказано, что подграф, индуцированный множеством точек, является кликой, кокликой или сильно регулярным графом (А.Л. Гаврилюк, А.А. Махнев [1]). Для графа диаметра 3 установлено, что указанная конструкция является 2-схемой для любой вершины a тогда и только тогда, когда граф дистанционно регулярен и для любой вершины a подграф Γ 3 ( a ) является кликой, кокликой или сильно регулярным графом.

Интересным представляется вопрос о существовании дистанционно регулярного графа с массивом пересечений {60 , 45 , 8;1 , 12 , 50}, для которого Γ 3 ( a ) может быть 6×6-решеткой и пара (Γ 3 ( a ) , Γ 2 ( a )) будет 2-схемой.

В [2] найдены возможные автоморфизмы дистанционно регулярного графа с массивом пересечений {60 , 45 , 8;1 , 12 , 50}. Дистанционно регулярный граф с массивом пересечений {60 , 45 , 8;1 , 12 , 50} назовем графом Гаври-люка.

В [3] было доказано, что граф Гаврилюка не существует. Однако в этой работе были допущены ошибки. Мы дадим корректное доказательство этого результата.

Теорема 1. Дистанционно регулярный граф с массивом пересечений {60,45,8;1,12,50} не существует.

• 1.    Тройные числа пересечений

В доказательстве теорем используются тройные числа пересечений [4].

Пусть Γ – дистанционно регулярный граф диаметра d, u1, u2, u3 – вершины графа Γ, r1, r2, r3 – неотрицательные целые числа, не

U1U2U3) большие d . Через {       } обозначим множе-

I rir2r3 )

ство вершин w 6Г таких, что d ( w,U i )= r i , а через г U 1 U 2 U31                       ₍'U₁U₂U₃')

L r1r2r3 J - число вершин в I r1r2r3 ? г U1U2U3-|

Числа [ _{r r г} ] называются тройными числами пересечений. Для фиксированной г U 1 U 2 U3I тройки вершин и 1 , и 2 , и 3 вместо I „ „ „ I бу-

L ' 1 ' 2 ' 3 J дем писать [ r 1 r 2 r 3 ]. К сожалению, для чисел

[ r 1 r 2 r 3 ] нет общих формул.

Однако в [4] предложен метод вычисления некоторых чисел [ r 1 r 2 r 3 ].

Пусть u, v, w – вершины графа Γ, W = d ( u,v ) , U = d ( v,w ) , V = d ( u,w ). Так как имеется точно одна вершина x = u такая, что d ( x,u )=0, то число [0 jh ] равно 0 или 1. Отсюда [0 jh ]= δ jW δ hV . Аналогично: [ i 0 h ]= δ iW δ hU и [ ij 0] = δ iU δ jV .

Другое множество уравнений можно получить, фиксируя расстояние между двумя вершинами из {u,v,w} и сосчитав число вер- шин, находящихся на всех возможных расстояниях от третьей:

( ^[lih]=v4_h-[0jh] \x f [Hh]=pl_l-[i0h] (+).

I Sftijl] = <-[ij0]

При этом некоторые тройки исчезают. При |i-j | >W или i+jр™ = 0, поэтому [ijh]=0 для всех h 6{0,_,d}.

Положим

г UVWI

[ ihl ]

, Q=r 2 (u) и Л=Г 2 (^). Тогда Л - регуляр

ный граф степени Р 2₂ = 160 на k 2 =225 верши

нах. Заметим, что для нашего графа Л=Й 2 .

d

_  Г UVW1

Q ri Q s j Q th ^[ у. $£ ^] , r,s,t=0

где Q ij - элементы дуальной матрицы собственных значений Q .

Если параметр Крейна q ^ = 0 , то S ijh ( u,v,w )=0.

Зафиксируем вершины u, v, w дистанционно регулярного графа Γ диаметра 3 и поло

,   ,   (UVW)   r ,   [UVW1

^{жим {ijh}} =^{ ijh }, [ijh] = ^[ ijh ], [ijh] = г UVW-I  ..       [UVWi ..       [UVWi

[ ihj ], [ijh] = [ jih ] и [ijh]  = [ hji \

Вычисление [ijh] ' , [ijh] * и [ijh] ~ (симметризация массива тройных чисел пересечений) может дать новые соотношения, позволяющие доказать несуществование графа.

2. Граф с массивом пересечений {60, 45, 8; 1, 12, 50}

Дистанционно регулярный граф Γ с массивом пересечений {60, 45, 8; 1, 12, 50} является Q -полиномиальным, имеет спектр 60¹,14⁴⁵,0²⁰⁷,-10⁶⁹, 1+60+225+36=322 вершин и дуальную матрицу собственных значений (см. [5]):

/

Q =

1 \1

-1

—

\

Лемма 2. Пусть d(u, v)=d(u, w)=2, d(v, w)=1. Тогда верны равенства:

[111]= r 4 , [112]=[121]=- r 4 +12 ,

[122]= r 3 + r 4 +20 ; [123]=[132]=- r 3 +8 , [133]= r 3 ;

[211 ]= r 3 - r 4 +10 , [212]=[221]=- r 3 + r 4 +29 , [222]=109 , [223]=[232]= r 3 - r 4 +22 , [233]= r 4 - r 3 +2 ;

[311]=- r 3 +4 , [312]=[321]= r 3 +4 , [322]=- r 3

• - r 4 +20 , [323]=[332]= r 4, [333]=- r 4 +4 , где r 3 e{0 , 1 ,..., 4} , r 4 6{0 , 1 ,..., 4} .

Доказательство. Решая систему линейных уравнений, заданных формулами (+) с учетом равенств S из( и, v, w )= S 131 ( и, v, w ) = S 311 ( u, v, w ) = 0, и вводя независимые переменные r з =[133], r 4 =[111], получим равенства из заключения леммы.

По лемме 2 имеем [222]=109.

Лемма 3. Пусть d(u, v)=d(u, w)=2, d(v, w)=3. Тогда верны равенства:

[112]= r 13 , [113]=- r 13 +12 , [121]= r 12 +8 , [122]=

• - r 12 - r 13 +З6 , [123]= r 13 -4 , [131]=- r 12 +4 ,

[132]= r 12 +4 ;

[212]= r 12 -r 1з +42 , [213]=- r 12 + r 13 -2 , [221]=- r 12

+ r 13 +26 , [222]=109 , [223]= r 12 - r 13 +25 , [231]= r 12 - r 13 +14 , [232]=- r 12 + r 13 +9 ;

[312]=-r 12+8, [313]= r 12, [321]=-r 13+16, [322]=r 12+r 13+4, [323]=-r 12+4, [331]=16-r 13, [332]=-r 13+12, где r 12e{0, 1,..., 4}, r 1зЕ{8, 9,..., 12}.

-

2 /

Ввиду границы Дельсарта порядок клики в Γ не больше 7. Многочлен Тервиллигера [6] равен (x² +44)(x+4)(x-4), поэтому собственные значения локального подграфа Г( и ) содержатся в [-4,4] U {14} и граф Г 2 сильно регулярен с параметрами (322,225,160,150).

Лемма 1. Г имеет числа пересечений:

Р 11 = 14,Р 12 = 45,Р 12 = 150,Р 13 = 30,Р¹ 3 = 6;

Р 21 = 12,Р 22 = 40,Р 23 = 8,Р 22 = 160,Р 23 = 24,Р 23 = 4;

Р 32 = 50,Р 33 = 10,Р 32 = 150,Р 33 = 25, Р 33 = 0.

Доказательство. Прямые вычисления.

Пусть u, v, w - вершины графа Г, [ihl] =

Доказательство. Упрощение формул (+) как в доказательстве леммы 2.

По лемме 3 имеем [222]=109.

Напомним,    что     Р 2₂ = 40, Р 2₂ =

160,Р 23 = 24.

Для числа ребер e между Л(v) и Л2(v) в графе    Λ    выполняется    равенство e=40 4 09+24 4 09=6976.

С другой стороны, имеем e =160(159- 2 ), где 2 - среднее значение параметра 2 (Л), следовательно, 159- 2 =43 . 6 и 2 =115 . 4.

Лемма 4. Пусть d(u, v) = d(u, w) = d(v, w) =2. Тогда верны равенства:

[111]=(-3 r 10 + r 7 + r 8 -3 r 9 ) / 4- r 11 +12 , [112]= r 9 , [113]=(3 r 10 - r 7 - r 8 - r 9 ) / 4+ r 11 , [121]=( r 10 - r 7 + r 8 + r 9 ) / 2 , [122]=- r 8 - r 9 +40 , [123]=(- r 10 + r 7 + r 8 + r 9 ) / 2 , [ 1 3 1]=( r 10 + r 7 - 3 r 8 + r 9 ) / 4+ r 11 , [132]= r 8 , [133]=(- r 10 - r 7 - r 8 - r 9 ) / 4- r 11 +8 ; [211]=(3 r 10 - r 7 - r 8 +3 r 9 ) / 4 , [212]=(- r 10 - r 7 + r 8 -3 r 9 ) / 2+40 , [213]=(- r 10 +З r 7 - r 8 +3 r 9 ) / 4 , [221]=

(-3 r 10 + r 7 - r 8 - r 9 ) / 2+40 , [222]= r 10 + r 7 + r 8 + r 9 +95 , [223]=( r 10 -3 r 7 - r 8 - r 9 ) / 2+24 , [231]=(3 r 10 - r 7 +3 r 8 - r 9 ) / 4 , [232]=(- r 10 - r 7 - 3 r 8 + r 9 ) / 2+24 , [233]=(- r 10 +3 r 7 +3 r 8 - r 9 ) / 4 ;

[311]= r 11 , [312]=( r 10 + r 7 - r 8 + r 9 ) / 2 , [313]=(- r 10 - r 7 + r 8 - r 9 ) / 2- r 11 +8 , [321]= r 10 , [322]=24- r 10 - r 7 , [323]= r 7 , [331]=- r 10 - r 11 +8 ,

[332]=(r10+r7+r8+r9)/2-4, [333]=(r10-r7- r8+r9)/2+r11-4, где r?е{0, 1, ..., 4}, r8, rio, r116 {0, 1, ..., 8}, r9Ё{0, 1, ..., 12}, r7+r8+r9+r 10 делится на 4.

Найдем число g 2 пар вершин (y, z) на рас-

стоянии 2, где y 6

{2u3v}

и z6

{2u2v}

. По лемме

имеем [222]=109, поэтому g2 = 24 • 109 =

2616. С другой стороны, по лемме 4 имеем

[232] = (—r₁₀ — r₇ — 3r₈ + r₉)/2 + 24 , поэтому g 2 = — E i (r 10 + r 7 + 3r 8 — r 9 )/2 + 3840 = 2616, ^(г 1 ₀ + r 7 + 3r 8 — r 9 )/2 = 1224 и X i (ri ₀ + r 7 + 3^ 8 — г₉ ' )/160 = 15.3.

Найдем число g 3 пар вершин ( y, z ) на рас-

Доказательство. Упрощение формул (+) как в доказательстве леммы 2.

По лемме 4 имеем

95≤[222]=r 10 +r 7 +r 8 +r 9 +95≤127.

Пусть d(u, v)=2.

стоянии 3, где у 6

UV) {23}

и z 6

UV) {22}

. По лемме

имеем [223]=Г 12 -Г 1з +25, где r 12 6{0, 1, ..., 4},

Найдем число f 1 пар вершин (y, z) на рас-

стоянии 1, где y 6

(uvi

^{21^{} и z 6}

{UV}

. По лемме 2

имеем [221]=-г з +г д +29, где г з 6{0, 1, ..., 4}, г д €{0, 1, ..., 4}, поэтому 1000=40·25≤f 1 ≤40·33=1320. С другой стороны, по лемме 4 имеем [211] = (3r₁₀ — r₇ — r₈ + 3r₉)/4 , поэтому 1000 < f 1 = ^sr Lo -r T -r ^ +sr⁹ < 1320, и 25 < S i (3r 1 ₀ — r 7 — r 8 + 3r 9 )/40 < 33.

Найдем число f 2 пар вершин (y, z) на рас-

стоянии 2, где y 6

uv

{21}и z 6

{2u2v}

. По лемме 2

имеем [222]=109, поэтому f 2 =40·109=4360. С

другой стороны, по лемме 4 имеем [212] =

(—r₁₀ — r₇ + r₈ — 3r₉)/2 + 40 , поэтому f₂ = — S_i(r 1 ₀ + r 7 — r 8 + 3r 9 )/2 + 6400 = 4360 , S i (r 1o + r 7 — r 8 + 3r 9 )/2 = 2040 и S i (r lo + r 7 — r 8 + 3r 9 )/160 = 25.5.

Найдем число f 3 пар вершин (y, z) на рас-

Г1з6{8, 9, ..., 12}, поэтому 312 = 24 • 13 < д3 < 24 • 29 = 696 . С другой стороны, по лемме 4 имеем [233] = (—г10 + 3г7 + 3г8 — г9)/4 , поэтому 312 <дз= ^(—г^ + 3г7 + 3г8 — г9)/4 < 696 и 7.8 < Е;(3Г10 — г7' + 3г8 — г9')/160 < 17.4. С учетом неравенства 13.2 < £К3г10 — г7 + 3г‘ — г')/160 < 22.8 получим     13.2 < £j(3r1i0 — г7' + 3г8' — г9')/

160 < 17.4.

Вычитая из Е ; (Г1₀ + г₇ — Г 8 + 3г₉)/ 160 = 25.5 равенство SiGw + г 7 + 3г₈ ' — г₉ ' )/ 160 = 15.3, получим £ ; (г₉ — г 8 )/160 = 2.55. Сложив 25 < Е ; (3Г 1 ₀ — г₇ ' — г 8 + 3г₉ ' )/40 < 33 с 13.2 < £ , (3г ‘ ₀ — г 7 + 3г₈ ' — г 9) /160 < 22.8, получим 38.2 <  £ ( (6г '₀ — 2г 7 + 2г₈ ‘ — 2г ' )/160 < 55.8 и 21.65 < £ , (3г'₀ —г ' )/ 160 < 30.45. Так как r₇6{0, 1, ..., 4}, гю6{0, 1, ..., 8}, то 21.65 < £ , (3г'₀ — г ‘ )/160 < 24.

Из неравенств 13.2 < £ ' (3г₁ ' ₀ — г 7 + 3г₈ ' — г₉ ' )/160 < 17.4, 21.65 < £ ' (3^ 0 — г₇ ' )/ 160 < 24 следует, что 8.45 < £ ; (г₉ — 3г₈ ' )/ 160 < 6.6 - противоречие. Теорема 1 доказана.

стоянии 3, где y 6

uv

^{21^{} и z 6}

{2u2v}

. По лемме 2

имеем [223]=г з -Г 4 +22, где г з 6{0, 1, ..., 4}, г д 6{0,

1, ..., 4}, поэтому 720 = 40 • 18 < f₃< 40 • 26 = 1040. С другой стороны, по лемме 4 имеем [213] = (—r₁₀ + 3r₇ — r₈ + 3r₉)/4, поэтому 720 < f₃ = E i (—r 1 ₀ + 3r 7 — r 8 + 3r 9 )/ 2 < 1040 и 9 < X i (—r 10 + 3r 7 — r 8 + 3r 9 )/ 160 = 13.

Найдем число g 1 пар вершин (y, z) на рас-

стоянии 1, где y 6

{2u3v}

и z 6

{2u2v}

. По лемме

имеем [221]=-Г 12 +г 1з +26, где r 12 6 {0, 1, ..., 4},

Г 1з 6{8, 9, ..., 12}, поэтому 528 = 24 • 22 < g 1 <

24^38 = 912. С другой стороны, по лемме 4 имеем [231] = (3r₁₀ — r₇ + 3r₈ — r₉)/4, поэтому 528 < g 1 = Z i (3r 10 — r 7 + 3r 8 — r 9 )/4 < 912 и 13.2 < Z_i(3r 1 ₀ — r 7 + 3r 8 — r 9 )/160 = 22.8 .