Clique containment

Definition

Let [math]N \gt 0 [/math] be an integer, and and [math]n = N \choose 2[/math] the number of possible edges in a graph with [math]N[/math] vertices. In this way, every [math]x \in \{-1,1\}^n[/math] describes a graph on [math]N[/math] vertices, with [math]x_i = 1[/math] if and only if the [math]i[/math]-th edge appears in the graph.

Let [math]k \gt 0[/math] be an integer. The k-clique containment function is the function [math]f_k : \{-1,1\}^n \to \{-1,1\}[/math] such that [math]f_k(x) = 1 [/math] if and only if the graph described by [math]x[/math] contains a clique of size [math]k[/math].

For a fixed value of [math]k[/math], as [math]n \to \infty[/math], the function [math]f_k(x)[/math] almost always takes the value [math]1[/math]. Thus [math]k[/math] must grow with [math]n[/math]; as it turns out, the proper scaling (that doesn't make [math]f_k(x)[/math] degenerate) is [math]k \approx \log(n)[/math]. Sometimes the phrase "clique containment" refers to the function [math]f_k[/math] for this specific choice of [math]k[/math].

Note: Even for the choice of [math]k[/math] above, the function [math]f_k(x)[/math] is non-degenerate only for some sequence of [math]n[/math].

Properties

• Clique containment is noise sensitive.

• Clique containment has revealment bounded away from 0.