Lower bounds for the size of random maximal H-free graphs

zbMATH Open1178.05088arXiv0805.1747MaRDI QIDQ1010905FDOQ1010905

Authors: Guy Wolfovitz 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the next greedy randomized process for generating maximal H-free graphs: Given a fixed graph H and an integer n, start by taking a uniformly random permutation of the edges of the complete n-vertex graph. Then, construct an n-vertex graph, M_n(H), iteratively as follows. Traverse the permuted edges of the complete n-vertex graph and add each one to the (initially empty) evolving graph M_n(H) - unless its addition creates a copy of H. The result of this process is a maximal H-free graph M_n(H). The basic question we are concerned with in here is: What is the expected number of edges in M_n(H)? We give new lower bounds on the expected number of edges in M_n(H) for the case where H is a regular, strictly 2-balanced graph. In particular, we obtain new lower bounds for Turan numbers of complete balanced bipartite graphs K_{r,r}, for every fixed r > 4. This improves an old lower bound of Erdos and Spencer.

Full work available at URL: https://arxiv.org/abs/0805.1747

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The early evolution of the \(H\)-free process
• Random maximalH-free graphs
• The triangle-free process
• The reverse \(H\)-free process for strictly 2-balanced graphs
• Dense subgraphs in the \(H\)-free process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35)

Cited In (14)

• The diamond-free process
• Dynamic concentration of the triangle‐free process
• Title not available (Why is that?)
• Random maximalH-free graphs
• Lower bound for the size of maximal nontraceable graphs
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• The early evolution of the \(H\)-free process
• The Reverse H‐free Process for Strictly 2‐Balanced Graphs
• A note on projective norm graphs
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• 4-cycles at the triangle-free process
• The Kőnig graph process
• Turán's theorem for pseudo-random graphs

This page was built for publication: Lower bounds for the size of random maximal \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010905)