Lema de regularidad para gráficos dispersos

El lema de regularidad de Szemeredi dice que cada gráfico denso puede aproximarse como una unión de $O(1)$ muchos gráficos expansores bipartitos. Más exactamente, hay una partición de la mayoría de los vértices en conjuntos $O(1)$ tal manera que la mayoría de los pares de conjuntos forman expansores bipartitos (el número de conjuntos en la partición y el parámetro de expansión dependen del parámetro de aproximación):

http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma

Hay versiones de este lema para gráficos dispersos de "buen comportamiento", ver, por ejemplo:

http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf

http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf

Lo que me sorprende de estas formulaciones es que solo garantizan que la mayoría de los pares de conjuntos en la partición forman expansores bipartitos, y estos expansores bipartitos pueden estar vacíos. Por lo tanto, en gráficos dispersos en general, es bastante posible que todos los bordes entre diferentes partes en la partición de los vértices no pertenezcan a un expansor.

Me pregunto si hay formulaciones que dan que la mayoría de los bordes entre las partes son de un expansor, o si no hay esperanza para tal formulación.

A continuación hay una respuesta larga, pero tl; dr en el caso general no hay esperanza para tal formulación, pero para muchas de las clases particulares de gráficos dispersos que tienen lemas de regularidad, esta formulación existe.

$\varepsilon > 0$$n$$G = (V, E)$$V = V_0 \cup V_1 \cup \dots \cup V_p$$p = O_{\varepsilon}(1)$

• $|V_0| \le \varepsilon n$$V_1, \dots, V_p$$1$$V_0$$\varepsilon p^2$$(V_i, V_j)$

  $$\left|d(S, T) - d(V_i, V_j)\right| < \varepsilon \text{ for all } S \subseteq V_i, T \subseteq V_j$$ $d(\cdot, \cdot)$

• $$\mathop{disc}(V_i, V_j) := \max \limits_{S \subseteq V_i, T \subseteq V_j} |V_i||V_j|\left|d(V_i, V_j) - d(S, T)\right|,$$ $$\sum \limits_{i, j =0}^p \mathop{disc}(V_i, V_j) < \varepsilon n^2.$$

El "fraseo combinatorio" (acabo de inventar estos nombres, no son estándar) es el original y probablemente más famoso, mientras que el "fraseo analítico" es más moderno y está relacionado con límites de gráficos, etc. (creo que se popularizó aquí) Para mí, el analítico es la formalización correcta del "gráfico aproximado por la unión de expansores bipartitos", ya que proporciona un control sobre el "error" total de tal aproximación, y no existe un conjunto excepcional para ocultar la masa. Pero en este punto esto es solo cosmético, porque es un lema fácil pero importante de que estas dos frases son equivalentes. Para pasar de Combinatorio a Analítico, solo la unión limita la contribución a la discrepancia de las partes irregulares y el conjunto excepcional. Para pasar de Analítico a Combinatorio, simplemente mueva cualquier parte que contribuya con demasiada discrepancia al conjunto excepcional y aplique la Desigualdad de Markov para controlar su masa.

Ahora para escasa regularidad. El objetivo de la regularidad escasa es reemplazar la en los respectivos desigualdades con , donde es la fracción de todos los bordes posibles presentan en . Críticamente, con este cambio, las dos frases ya no son equivalentes. Más bien, la redacción analítica es más fuerte: todavía implica Combinatoria exactamente como antes, pero Combinatoria generalmente no implica Analítica, porque (como se anticipa en el OP) uno puede ocultar mucha densidad en el conjunto excepcional o entre lo no regular pares de partes De hecho, esta separación es formal: los gráficos de límite inferior para el SRL denso (digamos, este$\varepsilon$$\varepsilon d(G)$$d(G)$$G$) implican que la Frase analítica no se extiende en general a gráficos dispersos, pero el documento de Scott vinculado en el OP muestra que la Frase combinatoria en realidad se extiende a todos los gráficos dispersos sin condiciones.

La encuesta vinculada en el OP se refiere principalmente a una SRL para gráficos dispersos "superiores regulares", lo que significa que el gráfico no tiene cortes que sean más densos que el promedio en más de un factor constante. Para estos gráficos en particular, los enunciados combinatorios y analíticos son equivalentes, porque no puede haber demasiada masa adicional oculta en las partes excepcionales, por lo que su contribución a la discrepancia puede estar limitada por la unión como en el caso denso. Entonces, estos gráficos tienen una interpretación "aproximada por unión de expansores bipartitos".

Finalmente, debo mencionar que hay muchas otras hipótesis en la literatura que también implican equivalencia entre estas frases. Por ejemplo, Upper Regularity (definida aquí ) es más general que Upper Regularity y aún es suficiente para implicar equivalencia. Sin embargo, para esta clase de gráficos y otras, solo soy consciente de los lemmas de regularidad débiles asociados .$L_p$