Существуют ли для любых двух неизоморфных графов

12

Я хочу быть очень конкретным. Кто-нибудь знает опровержение или доказательство следующего предложения:

pZ[x],n,k,CN,

G,HSTRUC[Σgraph](min(|G|,|H|)=n,GH),

φL(Σgraph),

|φ|p(n)qd(φ)Clog(n)kGφHφ.

Интуитивно понятно, что это должно быть правдой, если все неизоморфные графы можно различить с помощью операторов « local», и я думаю, что это неверно. Конечно, любой граф можно отличить, используя глубину полиномиального квантификатора, так как вы можете просто указать свой граф по модулю изоморфизма:Clog(n)k

φ=x1x2x3...xn(x(iVGx=xi)((i,j)EGE(xi,xj)))((i,j)EG¬E(xi,xj)))((i,j)VG2ijxixj).

Изменить: Так что кажется, что интуиция местности у меня была ложная. Формула квантификатора глубины имеет локальность Гайфмана, ограниченную O ( 3 k ) , что означает, что формула логарифмической глубины в основном глобальная. По этой причине у меня есть предчувствие, что предложение окажется верным, что, на мой взгляд , будет гораздо сложнее доказать.kO(3k)

Сэмюэль Шлезингер
источник
n2
1O(logn)
Высокие деревья могут работать на опровержение, если они отличаются близко к листьям.
Саламон
@ EmilJeřábek это правда без равенства?
Сэмюэль Шлезингер
1
@StellaBiderman Истинность формул без равенства сохраняется с помощью сюръективного отражения (т.е. сохранения отношений в обоих направлениях) гомоморфизмов. Например, в случае графов любые два графа без ребер удовлетворяют одним и тем же предложениям. В более общем смысле можно взять любой граф и взорвать любую вершину в самостоятельный набор.
Эмиль Йержабек

Ответы:

9

Спасибо моему коллеге Максиму Жуковскому за предложенный ответ.

G=KmKm¯H=Km+1Km1¯n=2mG=KmKm+1¯H=Km+1Km¯n=2m+1KssKs¯smm+1

nn+32

Даниил Мусатов
источник