Какие параметры графа НЕ сосредоточены на случайных графах?

23

Хорошо известно, что многие важные параметры графа показывают (сильную) концентрацию на случайных графах, по крайней мере, в некотором диапазоне вероятности границы. Некоторые типичные примеры: хроматическое число, максимальная клика, максимальный независимый набор, максимальное совпадение, номер доминирования, количество копий фиксированного подграфа, диаметр, максимальная степень, номер выбора (число окраски списка), номер Lovasz θ , ширина дерева, и т.п.

Вопрос: Какие исключения, то есть значимые параметры графов, не сосредоточены на случайных графах?

Редактировать. Возможное определение концентрации:

Xnnϵ>0

limnPr((1ϵ)E(Xn)Xn(1+ϵ)E(Xn))=1.
Xnp
limnPr(E(Xn)XnE(Xn))=1
который является кратчайшим возможным интервалом (так как степень является целым числом, но ожидаемое значение может не быть).

Примечание: можно создать искусственные исключения из правила концентрации. Например, пусть , если граф имеет нечетное число ребер, и 0 в противном случае. Это явно не сконцентрировано, но я бы не стал считать это значимым параметром.Xn=n

Андрас Фараго
источник
5
Пожалуйста, дайте определение сильной концентрации на случайных графиках.
Мохаммед Аль-Туркистани
Вероятно, определение «очень высокая вероятность (1-exp), что параметр находится в определенном (малом) диапазоне».
Суреш Венкат
@ MohammadAl-Turkistany Я отредактировал вопрос, чтобы включить определение.
Андрас Фараго
возможно простое бинарное свойство (свойства) как связность? или может быть идея исключить бинарные свойства? думаю, что это, возможно, требует лучшего анализа модели случайных графов. для графов эрдос-рени ( разве это не то, что вы имеете в виду?), сама связность проходит через пороговое явление.
vzn
2
Должна ли концентрация происходить только в ожидании? Я думаю, что количество копий фиксированного подграфа сконцентрировано, но не соответствует ожидаемому, если H не сбалансировано. HH
Аравинд

Ответы:

7

Многие параметры наибольшего связного компонента не концентрируются для G(n,p) если p=1/n и в более общем случае, если p находится в критическом окне. Примерами являются диаметр и размер самого большого компонента, размер второго по величине компонента, количество листьев, которое имеет компонент, и т. Д.

См. Например

Олдос, Дэвид. «Броуновские экскурсии, критические случайные графы и мультипликативный коалесцент». Анналы вероятности (1997): 812-854.

Начмиас, Асаф и Юваль Перес. «Критические случайные графики: диаметр и время перемешивания». Анналы вероятности 36, нет. 4 (2008): 1267-1286.

Аддарио-Берри, Луиджи, Николя Брутин и Кристина Гольдшмидт. «Континуальный предел критических случайных графов». Теория вероятностей и смежные области 152, нет. 3-4 (2012): 367-406.

Юваль Перес
источник
6

Неспособность сконцентрироваться происходит для некоторых счетных ( ) свойств, а может и для многих из них.#P

Простым примером является количество охватывающих подграфов ( ). Число ребер случайного граф флуктуирует ± & thetas ; ( п ) , так что число остовных подграфов колеблются с коэффициентом 2 & thetas ; ( п ) , а вдали от ( 1 + ε ) фактора используется в вашем определении концентрации ,2m±Θ(n)2Θ(n)(1+ϵ)

Чтобы показать, что это не единичный пример, вот аргумент (не совсем строгий, но, возможно, его можно сделать строгим) о том, почему неспособность сконцентрироваться также должна быть верной для числа гамильтоновых циклов. Ожидаемое значение этого числа ясно : каждый из ( n - 1 ) ! / 2 циклические последовательности вершин имеет 1 / 2 н шанс на самом деле является гамильтонов цикл. По аналогичному аргументу ожидаемое количество изменений этого числа, вызванное введением нового ребра, будет ((n1)!/2n+1(n1)!/21/2n , меньше на линейный коэффициент. Если бы число гамильтоновых циклов было сильно сконцентрировано, большинство переворотов по краям вызвало бы изменение этого числа, близкое к его ожидаемому значению. Но тогда Θ ( n ) флуктуация числа ребер вызовет флуктуацию числа гамильтоновых циклов, пропорциональную ожидаемому значению, что противоречит предположению о сильной концентрации.(n2)!/2n1Θ(n)

Другие вероятные кандидаты на неспособность сконцентрироваться включают количество раскрасок (разбиение вершин на независимые наборы), количество сопоставлений или совершенных сопоставлений или количество связующих деревьев.

Дэвид Эппштейн
источник
2
n
1
Было бы также интересно найти естественные свойства, которые не концентрируются даже в модели случайных графов G (n, m); те, что в этом ответе, работают только для G (n, p).
Дэвид Эппштейн
Ответы Дэвида на «подсчет аргументов» всегда так проницательны для меня. : D
Даниэль Апон