The K_4-free process

Details The K_4-free process The K_4-free process

2010-08-24

arxiv.org/abs/1008.4044v1

Mathematics

Combinatorics

36 pages

Scientific paper

We consider the K_4-free process. In this process, the edges of the complete n-vertex graph are traversed in a uniformly random order, and each traversed edge is added to an initially empty evolving graph, unless the addition of the edge creates a copy of K_4. Let M(n) denote the graph that is produced by that process. We prove that a.a.s., the number of edges in M(n) is O( n^{8/5} (\ln n)^{1/5} ). This matches, up to a constant factor, a lower bound of Bohman. As a by-product, we prove the following Ramsey-type result: for every n there exists a K_4-free n-vertex graph, in which the largest set of vertices that doesn't span a triangle has size O( n^{3/5} (\ln n)^{1/5} ). This improves, by a factor of (\ln n)^{3/10}, an upper bound of Krivelevich.

Affiliated with

Also associated with

No associations

Rating

The K_4-free process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The K_4-free process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The K_4-free process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393904