Хорошо известно, что многие важные параметры графа показывают (сильную) концентрацию на случайных графах, по крайней мере, в некотором диапазоне вероятности границы. Некоторые типичные примеры: хроматическое число, максимальная клика, максимальный независимый набор, максимальное совпадение, номер доминирования, количество копий фиксированного подграфа, диаметр, максимальная степень, номер выбора (число окраски списка), номер Lovasz , ширина дерева, и т.п.
Вопрос: Какие исключения, то есть значимые параметры графов, не сосредоточены на случайных графах?
Редактировать. Возможное определение концентрации:
Примечание: можно создать искусственные исключения из правила концентрации. Например, пусть , если граф имеет нечетное число ребер, и 0 в противном случае. Это явно не сконцентрировано, но я бы не стал считать это значимым параметром.
источник
Ответы:
Многие параметры наибольшего связного компонента не концентрируются дляG(n,p) если p=1/n и в более общем случае, если p находится в критическом окне. Примерами являются диаметр и размер самого большого компонента, размер второго по величине компонента, количество листьев, которое имеет компонент, и т. Д.
См. Например
Олдос, Дэвид. «Броуновские экскурсии, критические случайные графы и мультипликативный коалесцент». Анналы вероятности (1997): 812-854.
Начмиас, Асаф и Юваль Перес. «Критические случайные графики: диаметр и время перемешивания». Анналы вероятности 36, нет. 4 (2008): 1267-1286.
Аддарио-Берри, Луиджи, Николя Брутин и Кристина Гольдшмидт. «Континуальный предел критических случайных графов». Теория вероятностей и смежные области 152, нет. 3-4 (2012): 367-406.
источник
Неспособность сконцентрироваться происходит для некоторых счетных ( ) свойств, а может и для многих из них.#P
Простым примером является количество охватывающих подграфов ( ). Число ребер случайного граф флуктуирует ± & thetas ; ( п ) , так что число остовных подграфов колеблются с коэффициентом 2 & thetas ; ( п ) , а вдали от ( 1 + ε ) фактора используется в вашем определении концентрации ,2m ±Θ(n) 2Θ(n) (1+ϵ)
Чтобы показать, что это не единичный пример, вот аргумент (не совсем строгий, но, возможно, его можно сделать строгим) о том, почему неспособность сконцентрироваться также должна быть верной для числа гамильтоновых циклов. Ожидаемое значение этого числа ясно : каждый из ( n - 1 ) ! / 2 циклические последовательности вершин имеет 1 / 2 н шанс на самом деле является гамильтонов цикл. По аналогичному аргументу ожидаемое количество изменений этого числа, вызванное введением нового ребра, будет ((n−1)!/2n+1 (n−1)!/2 1/2n , меньше на линейный коэффициент. Если бы число гамильтоновых циклов было сильно сконцентрировано, большинство переворотов по краям вызвало бы изменение этого числа, близкое к его ожидаемому значению. Но тогда Θ ( n ) флуктуация числа ребер вызовет флуктуацию числа гамильтоновых циклов, пропорциональную ожидаемому значению, что противоречит предположению о сильной концентрации.(n−2)!/2n−1 Θ(n)
Другие вероятные кандидаты на неспособность сконцентрироваться включают количество раскрасок (разбиение вершин на независимые наборы), количество сопоставлений или совершенных сопоставлений или количество связующих деревьев.
источник