The generation of a random triangle-saturated graph via the triangle-free process has been studied extensively. In this short note our aim is to introduce an analogous process in the hypercube. Specifically, we consider the $Q_2$-free process in $Q_d$ and the random subgraph of $Q_d$ it generates. Our main result is that with high probability the graph resulting from this process has at least $cd^{2/3} 2^d$ edges. We also discuss a heuristic argument based on the differential equations method which suggests a stronger conjecture, and discuss the issues with making this rigorous. We conclude with some open questions related to this process.
@article{10_37236_8864,
author = {J. Robert Johnson and Trevor Pinto},
title = {The {\(Q_2\)-free} process in the hypercube},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/8864},
zbl = {1453.05121},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8864/}
}
TY - JOUR
AU - J. Robert Johnson
AU - Trevor Pinto
TI - The \(Q_2\)-free process in the hypercube
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8864/
DO - 10.37236/8864
ID - 10_37236_8864
ER -
%0 Journal Article
%A J. Robert Johnson
%A Trevor Pinto
%T The \(Q_2\)-free process in the hypercube
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8864/
%R 10.37236/8864
%F 10_37236_8864
J. Robert Johnson; Trevor Pinto. The \(Q_2\)-free process in the hypercube. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/8864
