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

Статья

Независимые множества общего вида в случайных сильно разреженных гиперграфах

Проблемы передачи информации. 2018. Т. 54. № 1. С. 63-77.
Шабанов Д. А., Семенов А. С.

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

αj(H(n,k,p))n−→Pγ(k,j,c) при n→+∞.


Более того, величина γ(k,j,c) предъявлена явно как функция от решения некоторого трансцендентного уравнения.