Я пытаюсь найти, насколько близки и , когда и является константой, не зависящей от n (поэтому ). Моя оценка такова: whp, но я не смог доказать это.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n...
Хорошо известно, что многие важные параметры графа показывают (сильную) концентрацию на случайных графах, по крайней мере, в некотором диапазоне вероятности границы. Некоторые типичные примеры: хроматическое число, максимальная клика, максимальный независимый набор, максимальное совпадение, номер...
Одна из интересных открытых проблем о DFA, перечисленных в разделе. Есть ли еще какие-либо открытые проблемы о DFA? размер DFA, необходимый для разделения двух строк длины . Мне любопытно, есть ли какие-либо результаты о способности случайного DFA разделять две заданные (неслучайные) строки.nNn...
Позволять G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) быть случайным графом на ≈n3/2≈n3/2\approx n^{3/2}кромки. С очень высокой вероятностью,GGG имеет много 444-циклов. Наша цель - вывести любой из этих444-циклы как можно быстрее. Предположим, у нас есть доступ к GGG в форме списка смежности, мы...