Cuando la función theta de Lovász satura su límite superior

Question

El Lovász $\vartheta$ -función de un gráfico $G$ , $\vartheta(G)$ es conocido por estar "intercalado" entre el número de independencia del grafo, $\alpha(G)$ y el número cromático de su complemento, $\chi (\overline{G})$ .

En $G$ es perfecto entonces $$\alpha(G)=\vartheta(G)=\chi (\overline{G}).$$

Me gustaría saber si existen gráficos $G$ tal que $$\alpha(G)< \vartheta(G)= \chi (\overline{G}).$$

Answer 1

Supongamos que $G$ es un $k$ -grafo regular en $n$ vértices, con el menor valor propio $\tau$ . Lovasz demostró que $$ \theta(G) \le \frac{n}{1-\frac{k}{\tau}}. $$ Además, si el grupo de automorfismo de $G$ actúa arco-transitivamente, entonces la igualdad se mantiene. De hecho, la igualdad se mantiene si G es una clase única en una configuración coherente homogénea, por ejemplo, si $G$ es un grafo fuertemente regular.

Clase 1: Gráfico del cuadrado latino. Tomemos el grafo cuyos vértices son los $n^2$ células de y $n\times n$ Cuadrado latino, en el que dos casillas son adyacentes si están en la misma fila, la misma columna o tienen el mismo contenido. Este grafo es regular con valencia $3(n-1)$ y el mínimo valor propio $-3$ y así $\theta(G)=n$ . Pero si el cuadrado latino es la tabla de multiplicar de un grupo cíclico de orden par, entonces $\alpha(G) < n$ (porque los cuadrados latinos cíclicos no tienen transversales, pero se puede encontrar una breve prueba en la página 225 de uno de mis favoritos libros favoritos de teoría algebraica de grafos). Los vértices de una columna determinada forman una camarilla de tamaño $n$ y así vemos que $\chi(\bar{G})=n$ para cualquier cuadrado latino de orden $n$ .

Clase 2: cuadrángulos generalizados: Un GQ con parámetros $(s,t)$ es una colección de puntos y líneas que satisfacen algunos axiomas, en particular cada línea contiene exactamente $s+1$ puntos. Considera adyacentes dos puntos si son colineales. Si $s,t>1$ se obtiene un grafo fuertemente regular en $(s+1)(st+1)$ vértices con valencia $s(t+1)$ y el mínimo valor propio $-t-1$ . Por lo tanto $\theta(G) = st+1$ y un coclip de tamaño $st+1$ se conoce como ovoide . Los puntos de la línea forman una camarilla de tamaño $s+1$ y un conjunto de líneas que dividen el conjunto de puntos se denomina difundir . De ahí que quiera GQ's con spreads pero sin ovoides. Para ejemplos reales, te remito al libro de Payne y Thas sobre GQ's---los GQ's $Q(5,q)$ trabajo.