Lemme de régularité pour les graphes clairsemés

Le lemme de régularité de Szemeredi dit que chaque graphe dense peut être approché comme une union de nombreux graphes expanseurs bipartis. Plus précisément, il existe une partition de la plupart des sommets en ensembles sorte que la plupart des paires d'ensembles forment des expanseurs bipartites (le nombre d'ensembles dans la partition et le paramètre d'expansion dépendent du paramètre d'approximation): $O(1)$ $O(1)$

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

Il existe des versions de ce lemme pour les graphiques clairsemés "bien se comporter", voir par exemple:

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

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

Ce qui me surprend dans ces formulations, c'est qu'elles garantissent uniquement que la plupart des paires d'ensembles de la partition forment des expanseurs bipartites, et ces expanseurs bipartites peuvent être vides. Ainsi, dans les graphes clairsemés, il est fort possible que toutes les arêtes entre les différentes parties de la partition des sommets n'appartiennent pas à un expanseur.

Je me demande s'il existe des formulations qui donnent que la plupart des bords entre les pièces proviennent d'un expanseur, ou s'il n'y a aucun espoir pour une telle formulation.

graph-theory co.combinatorics expanders Dana Moshkovitz
la source

mais ne semble-t-il pas intuitif que le thm, qui est pour les graphiques denses, se décompose à certains égards sur les graphiques clairsemés? notez que la référence wikipedia liée à ne dit rien sur les graphiques d'extension, ce qui suggère que cela pourrait en fait être une interprétation / formulation ultérieure ...

vzn

(1) Le terme habituel pour les paires d'ensembles qui se comportent bien est "paires régulières" (dans Wikipedia "paire" pseudo-aléatoire "). Je l'ai remplacé par des "expandeurs bipartites" car je trouve cette terminologie plus naturelle pour moi. Dans tous les cas, l'intention est que si vous choisissez des sous-ensembles suffisamment grands des deux côtés de la paire, le nombre d'arêtes entre les sous-ensembles est proportionnel au nombre d'arêtes de la paire. (2) Bien sûr, ce qui est vrai pour les graphiques denses peut cesser d'être vrai pour les graphiques clairsemés. Ma question porte exactement sur la mesure dans laquelle les propriétés du cas dense continuent de se maintenir dans le cas clairsemé.

Dana Moshkovitz

Voici une réponse longue, mais tl; dr dans le cas général, il n'y a aucun espoir pour une telle formulation, mais pour de nombreuses classes particulières de graphiques clairsemés qui ont des lemmes de régularité, cette formulation 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)$
$| d (S, T) - d (V_{i}, V_{j}) | < ε for all S \subseteq V_{i}, T \subseteq 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)$

$d i s c (V_{i}, V_{j}) := max_{S \subseteq V_{i}, T \subseteq V_{j}} | V_{i} | | V_{j} | | d (V_{i}, V_{j}) - d (S, T) |,$ $\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_{i, j = 0}^{p} d i s c (V_{i}, V_{j}) < ε n^{2} .$ $\sum \limits_{i, j =0}^p \mathop{disc}(V_i, V_j) < \varepsilon n^2.$

Le "phrasé combinatoire" (je viens de inventer ces noms, ils ne sont pas standard) est l'original et probablement le plus célèbre, alors que le "phrasé analytique" est plus moderne et lié aux limites des graphes, etc. (je pense qu'il a été popularisé ici). À mes yeux, l'analyse est la bonne formalisation du "graphique approximé par l'union des expanseurs bipartites", car elle donne un contrôle sur l '"erreur" totale d'une telle approximation, et il n'y a pas d'ensemble exceptionnel dans lequel cacher la masse. Mais à ce stade, ce n'est que cosmétique, car c'est un lemme facile mais important que ces deux phrasés soient équivalents. Pour passer du combinatoire à l'analytique, l'union juste a lié la contribution à la divergence des parties irrégulières et de l'ensemble exceptionnel. Pour passer d'Analytique à Combinatoire, déplacez simplement n'importe quelle partie qui apporte trop de divergence à l'ensemble exceptionnel et appliquez l'Inégalité de Markov pour contrôler sa masse.

Maintenant, pour une régularité clairsemée. Le but de la régularité clairsemée consiste à remplacer le dans les inégalités respectives avec , où est la fraction de tous les bords éventuels présents dans . Surtout, avec ce changement, les deux phrasés ne sont plus équivalents. Au contraire, le phrasé analytique est plus fort: il implique toujours Combinatorial exactement comme avant, mais Combinatorial n'implique généralement pas Analytique, car (comme prévu dans le PO), on peut potentiellement cacher beaucoup de densité dans l'ensemble exceptionnel ou entre le non régulier paires de pièces. En effet, cette séparation est formelle: les graphes de borne inférieure pour le SRL dense (disons celui-ci $\varepsilon$ $\varepsilon d(G)$ $d(G)$ $G$ ) impliquent que le phrasé analytique ne s'étend pas en général aux graphiques clairsemés, mais l'article de Scott lié dans l'OP montre que le phrasé combinatoire s'étend en fait à tous les graphiques clairsemés sans conditions.

L'enquête liée dans le PO parle principalement d'un SRL pour les graphiques clairsemés «supérieurs réguliers», ce qui signifie grosso modo que le graphique n'a pas de coupes plus denses que la moyenne de plus d'un facteur constant. Pour ces graphes particuliers, les phrasés combinatoire et analytique sont équivalents, car il ne peut pas y avoir trop de masse supplémentaire cachée dans les parties exceptionnelles, de sorte que leur contribution à la divergence peut être liée à l'union comme dans le cas dense. Ces graphiques ont donc une interprétation «approximée par l'union des expanseurs bipartites».

Enfin, je dois mentionner qu'il existe de nombreuses autres hypothèses dans la littérature qui impliquent également l'équivalence entre ces phrasés. Par exemple, Upper Regularity (défini ici ) est plus général que Upper Regularity et est encore suffisant pour impliquer une équivalence. Cependant, pour cette classe de graphes et d'autres, je ne connais que les lemmes de régularité faible associés . $L_p$

GMB
la source

Aussi, des excuses pour la nécromancie des threads - cela vient de s'aligner sur ma critique éclairée actuelle, et j'ai pensé partager ce que j'ai trouvé.

GMB

Lemme de régularité pour les graphes clairsemés

Réponses: