Плотность краев в теореме Семереди для построения графиков r - Математика
0 голосов
/ 04 мая

Я задал вопрос здесь , касающийся дополнительных предположений, которые необходимо сделать для краевых плотностей, и разрешений, сформированных в лемме о регулярности Семзереди, в порядке r fo r, который будет полезен для r лемма подсчета / построения (сколько копий графа можно найти). Мне сказали, что мой вопрос был unclea r (я согласен, что это было так), поэтому вот более конкретный пример, который, как мы надеемся, покажет мою путаницу:

Предположим, график $G$ orde r $n$ имеет $\alpha{n \choose 2}$ ребер. В orde r для «построения» графа $H$ в $G$, o r подсчитайте, сколько копий $H$ у нас в $G$, мы вспоминаем лемму здания:

Пусть H - граф с $\Delta (H) = d$, который имеет раскраску r, чтобы ни один цвет r не использовался более s раз. Тогда, если граф G состоит из классов вершин $V1_,...,V_r$ с $|V_i|=n$, таких что каждый pai r является $\epsilon$ равномерным и имеет взаимную плотность $d(V_i,jV)_\geq \lambda$.

Тогда, если $\lambda ^d \geq \epsilon (d+1)$ и $s\leq \lceil \epsilon n \rceil$, тогда G содержит копию f H.

Если по расширению, если каждый цвет r используется один раз в графе, например $K_r$, то лемма aboce гарантирует нам $K_r(s)$ с $s$, растущим линейно с $n$, и в котором есть $s^r$ копий $K_r$ (таким образом, счет).

Таким образом, чтобы использовать лемму счета, нам нужно найти $r$ взаимно $\epsilon$ однородных и достаточно больших по плотности $\lambda$ частей. Обратите внимание, что эти условия связаны: мы можем иметь дело с маленьким r $\lambda$, если у нас есть маленькое r $\epsilon$. Смутно, я путаюсь с тем, что для маленького r $\epsilon$ требуется больше частей в разделе Семереди, но я не вижу, как число r деталей с большой плотностью взаимных краев не растет достаточно быстро с числом r частей.

Теперь по лемме oSzemeredi говорит нам, что для r больших графов, мы можем найти $\epsilon$ равномерное распределение на ограниченном числе r частей. Это не заботится об абсолютной краевой плотности.

Если мы построим равномерное распределение ou r $\epsilon$ на $p$ деталях, мы получим не более $\epsilon p^2$ пар, не равномерных по эпсилону. Таким образом, для r любого $s$ мы можем гарантировать $K_s$ взаимно $\epsilon$ однородных пар, выбрав $\epsilon < \frac{1}{s-1}$. Так как у нас есть по крайней мере $(1-\frac{1}{s-1} +(\frac{1}{s-1} -\epsilon)){p\choose 2}$ однородных пар, что гарантирует $K_s$ Эрдосом Стоуном.

Но как насчет того, чтобы найти достаточно взаимно плотных пар среди взаимно $\epsilon$ однородных пар?

Мое мышление выглядит так:

  • Лемма Семезреди ничего не говорит нам о том, как мы распределили грани. Таким образом, в худшем случае у частей r p будет как можно больше ребер внутри классов. Это делает $p {n/p \choose 2}$ скрытыми ребрами.
  • Мы начали с $\alpha {n\choose 2}$ ребер. И это оставляет нас с $M = \alpha {n\choose 2} - p {n/p \choose 2}$. Обратите внимание, что это значение увеличивается с p с членом $-\frac{n^2}{2p}$.
  • Таким образом, средняя плотность между ou r частей составляет $\frac{M}{{p\choose 2} \cdot (\frac{n}{p})^2}$. Что, безусловно, все еще возрастает с p, но ...

Здесь я застрял на том, как убедить себя в том, что мы можем получить достаточно частей, чтобы доля пар плотности не $\lambda$ составляла ограниченный, скажем, $\delta$, и я могу сделать это настолько маленьким, насколько захочу. Это то, что я хотел бы, чтобы я мог сказать, что число r из $\epsilon$ однородных и $\lambda$ пар плотности по крайней мере $(1-\delta - \epsilon){p\choose 2}$. Итак, еще раз я могу гарантировать, что мой разыскиваемый $K_r$ будет использовать строительную лемму.

Я думаю, что уместным является тот факт, что полученные мной дроби, похоже, не зависят от $n$. Таким образом, я всегда могу предположить, что мой $n$ достаточно велик для * усреднения r, чтобы работать? Не уверен насчет этого.

Надеюсь, это понятно r, чем мой предыдущий пост.

Добро пожаловать на сайт Математика, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...