Four-clique threshold in a binomial 3-uniform hypergraph

ID: four-clique-threshold-in-a-binomial-3-uniform-hypergraph

A complete three-uniform hypergraph on four vertices has four edges. In the binomial random hypergraph , its count has mean . If , the first moment method gives . Two distinct four-sets have independent clique indicators unless they share three vertices; in that case their combined edge set has seven triples. There are such ordered pairs, so . Consequently if . The second moment method then gives . These two implications establish the threshold function.

New to topics? Read the docs here!