cover image: On the Intersecting Family Process

Premium

On the Intersecting Family Process

2024

It is interesting to note that, combining the results of [6], [7] and Theorem 2, for the whole regime k ≪ n5/12 we have that w.h.p. [...] If r = o(√log n) and Hr−1 is simple and has no vertices of degree at least 3 then the probability that Hr is not simple is O(1/k1−o(1)). [...] Once the two vertices of degree one in a common edge and S have been selected for E we have covered 1 + er(S) edges, so we have r − er(S) − 1 edges still to cover. [...] , Er, otherwise we say that it is closed, and let Or be the set of open edges at step r. [...] For r ≤ o(√log n), by step r we have not yet selected an edge not in I∗∗ and from then on the probability that we pick an edge outside of I∗∗ is at most n−ω(1). [...] For r ≤ nω(1) the probability at each step that we pick a set in D(E′) is at least k−(3r0+1+o(1)). [...] We show later in the proof of Theorem 9 that P(X = r + 1, SIMPLE(r)) = ζr for some ζr > 0. [...] In the case that r0 = 3 we see that S is consists of just a singleton set and it stabilizes at the third step of the process, so r1 = 3. [...] In this case I∗ = I∗∗ and is the star centered at that first vertex of degree three. [...] By the proof of Theorem 2 we can see that S is generated by Procedure 1 with input equal to c−3 for k = cnn1/3, cn → c.

Related Organizations

Pages
29
Published in
United States of America