Difference between revisions of "Clique containment"
(Created page with "== Definition == Let <math>N > 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,...") |
m (→Definition) |
||
| Line 4: | Line 4: | ||
Let <math>k > 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>. | Let <math>k > 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> | + | 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>. | 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>. | ||
Latest revision as of 14:11, 5 April 2021
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. [1]
- Clique containment has revealment bounded away from 0. [2]
References
- ↑ Problem I.9 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Proposition VIII.10 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
