Аннотация:
При $p=const$ в случайном графе Эрдёша–Реньи $G(n,p)$ наблюдается эффект двухточечной концентрации наибольшего размера индуцированного подграфа заданного класса для множества различных классов графов: независимых множеств, лесов, деревьев, циклов, графов ограниченной степени, графов с ограниченным числом рёбер и др. При $p\to0$ для тех же классов графов имеет место асимптотика наибольшего размера. В нашей работе рассмотрены новые классы графов, а именно, леса и деревья ограниченной степени, для которых также оказывается верна двухточечная концентрация.
|
