Clique containment

From Boolean Zoo
Jump to: navigation, search

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] [TODO: Cite]. 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


References

  1. Problem I.9 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
  2. Proposition VIII.10 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).