• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

О числах независимости случайных разреженных гиперграфов

Дискретная математика. 2016. Т. 28. № 3. С. 126-144.
Шабанов Д. А., Семенов А. С.

Изучается асимптотическое поведение числа независимости для биномиальной модели случайного k-однородного гиперграфа H(n, k, p) в разреженном случае, когда p = c (n-k)!(k-1)!/(n−1)! при положительном постоянном c > 0. Показано, что существует такая константа γ(c) > 0, что число независимости α(H(n, k, p)) подчиняется закону больших чисел α(H(n, k, p))/n → γ(c) при n → +∞. Доказано, что γ(c) > 0 является решением некоторого трансцендентного уравнения при малых значениях c ⩽ 1/(k − 1).