Graphs with few cliques

<h2 id="definition">Definition</h2>
A clique of a graph is a complete <a href="/facts/Subgraph_(graph_theory)/W0MqKkyE">subgraph</a>, while a maximal clique is a clique that is not properly contained in another clique. One can regard a clique as a cluster of vertices, since they are by definition all connected to each other by an edge. The concept of clusters is ubiquitous in <a href="/facts/Data_analysis/CNtARxLW">data analysis</a>, such as on the analysis of <a href="/facts/Social_network/kQg6aEVf">social networks</a>. For that reason, limiting the number of possible maximal cliques has computational ramifications for <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> on graphs or networks.
Formally, let 
 
 
 
 X
 
 
 {\displaystyle X}
 
 be a class of graphs. If for every 
 
 
 
 n
 
 
 {\displaystyle n}
 
-<a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 in 
 
 
 
 X
 
 
 {\displaystyle X}
 
, there exists a polynomial 
 
 
 
 f
 (
 n
 )
 
 
 {\displaystyle f(n)}
 
 such that 
 
 
 
 G
 
 
 {\displaystyle G}
 
 has 
 
 
 
 O
 (
 f
 (
 n
 )
 )
 
 
 {\displaystyle O(f(n))}
 
 maximal cliques, then 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is said to be a class of graphs with few cliques.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="examples">Examples</h2>
<ul><li>The <a href="/facts/Tur%25C3%25A1n_graph/y0hzJqQQ">Turán graph</a> 
 
 
 
 T
 (
 n
 ,
 ⌈
 n
 
 /
 
 3
 ⌉
 )
 
 
 {\displaystyle T(n,\lceil n/3\rceil )}
 
 has an <a href="/facts/Exponential_growth/m4yEqKJ7">exponential number</a> of maximal cliques. In particular, this graph has exactly 
 
 
 
 
 3
 
 n
 
 /
 
 3
 
 
 
 
 {\displaystyle 3^{n/3}}
 
maximal cliques when 
 
 
 
 n
 ≡
 0
 
 mod
 
 
 3
 
 
 {\displaystyle n\equiv 0\mod 3}
 
, which is <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotically greater</a> than any polynomial function.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>: 441  This graph is sometimes called the Moon-Moser graph, after Moon & Moser showed in 1965 that this graph has the largest number of maximal cliques among all graphs on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> So the class of Turán graphs does not have few cliques.</li>
<li>A <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> 
 
 
 
 T
 
 
 {\displaystyle T}
 
 on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly 
 
 
 
 n
 −
 1
 
 
 {\displaystyle n-1}
 
 edges,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>: 578  and therefore that number of maximal cliques. So the class of trees has few cliques.</li>
<li>A <a href="/facts/Chordal_graph/7hNerUdA">chordal graph</a> on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices has at most 
 
 
 
 n
 
 
 {\displaystyle n}
 
 maximal cliques,<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>: 49  so chordal graphs have few cliques.</li>
<li>Any <a href="/facts/Planar_graph/plREagr9">planar graph</a> on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices has at most 
 
 
 
 8
 n
 −
 16
 
 
 {\displaystyle 8n-16}
 
 maximal cliques,<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> so the class of planar graphs has few cliques.</li>
<li>Any 
 
 
 
 n
 
 
 {\displaystyle n}
 
-vertex graph with <a href="/facts/Boxicity/9aAIvmKe">boxicity</a> 
 
 
 
 b
 
 
 {\displaystyle b}
 
 has 
 
 
 
 O
 (
 
 n
 
 b
 
 
 )
 
 
 {\displaystyle O(n^{b})}
 
 maximal cliques,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>: 46  so the class of graphs with bounded boxicity has few cliques.</li>
<li>Any 
 
 
 
 n
 
 
 {\displaystyle n}
 
-vertex graph with <a href="/facts/Degeneracy_(graph_theory)/IaYkus22">degeneracy</a> 
 
 
 
 d
 
 
 {\displaystyle d}
 
 has at most 
 
 
 
 (
 n
 −
 d
 )
 
 3
 
 d
 
 /
 
 3
 
 
 
 
 {\textstyle (n-d)3^{d/3}}
 
 maximal cliques whenever 
 
 
 
 d
 ≡
 0
 
 mod
 
 
 3
 
 
 {\displaystyle d\equiv 0\mod 3}
 
 and 
 
 
 
 n
 ≥
 d
 +
 3
 
 
 {\displaystyle n\geq d+3}
 
,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> so the class of graphs with bounded degeneracy has few cliques.</li>
<li>Let 
 
 
 
 G
 
 
 {\displaystyle G}
 
 be an <a href="/facts/Intersection_graph/IehIvyR3">intersection graph</a> of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 <a href="/facts/Convex_polytope/2pRHcRgC">convex polytopes</a> in 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> whose <a href="/facts/Face_(geometry)/T2E6BTU4">facets</a> are parallel to 
 
 
 
 k
 
 
 {\displaystyle k}
 
 <a href="/facts/Hyperplane/2s2ycYYd">hyperplanes</a>. Then the number of maximal cliques of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is 
 
 
 
 O
 
 (
 
 n
 
 d
 
 k
 
 d
 +
 1
 
 
 
 
 )
 
 
 
 {\textstyle O\left(n^{dk^{d+1}}\right)}
 
,<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>: 274  which is polynomial in 
 
 
 
 n
 
 
 {\displaystyle n}
 
 for fixed 
 
 
 
 d
 
 
 {\displaystyle d}
 
 and 
 
 
 
 k
 
 
 {\displaystyle k}
 
. Therefore, the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley. <a href="https://www.worldcat.org/title/30781165" target="_blank">https://www.worldcat.org/title/30781165</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley. <a href="https://www.worldcat.org/title/30781165" target="_blank">https://www.worldcat.org/title/30781165</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Rosgen, B., & Stewart, L. (2007). Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science, Vol. 9 no. 1 (Graph and Algorithms), 387. https://doi.org/10.46298/dmtcs.387 <a href="https://doi.org/10.46298/dmtcs.387" target="_blank">https://doi.org/10.46298/dmtcs.387</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Fox, J., Roughgarden, T., Seshadhri, C., Wei, F., & Wein, N. (2020). Finding Cliques in Social Networks: A New Distribution-Free Model. SIAM Journal on Computing, 49(2), 448–464. https://doi.org/10.1137/18M1210459 <a href="https://doi.org/10.1137/18M1210459" target="_blank">https://doi.org/10.1137/18M1210459</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley. <a href="https://www.worldcat.org/title/30781165" target="_blank">https://www.worldcat.org/title/30781165</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete mathematics: a foundation for computer science (2nd ed.). Reading, Mass: Addison-Wesley. <a href="https://www.worldcat.org/title/29357079" target="_blank">https://www.worldcat.org/title/29357079</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024 <a href="https://doi.org/10.1007/BF02760024" target="_blank">https://doi.org/10.1007/BF02760024</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Pahl, P. J., & Damrath, R. (2001). Mathematical foundations of computational engineering: a handbook. Berlin ; New York: Springer. <a href="https://www.worldcat.org/title/47208580" target="_blank">https://www.worldcat.org/title/47208580</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1), 47–56. https://doi.org/10.1016/0095-8956(74)90094-X <a href="https://doi.org/10.1016/0095-8956(74)90094-X" target="_blank">https://doi.org/10.1016/0095-8956(74)90094-X</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Wood, D. R. (2007). On the Maximum Number of Cliques in a Graph. Graphs and Combinatorics, 23(3), 337–352. https://doi.org/10.1007/s00373-007-0738-8 <a href="https://doi.org/10.1007/s00373-007-0738-8" target="_blank">https://doi.org/10.1007/s00373-007-0738-8</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Spinrad, J. P. (2003). Intersection and containment representations. In Efficient graph representations (pp. 31–53). Providence, R.I: American Mathematical Society. <a href="https://www.worldcat.org/title/51848305" target="_blank">https://www.worldcat.org/title/51848305</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36 <a href="https://doi.org/10.1007/978-3-642-17517-6_36" target="_blank">https://doi.org/10.1007/978-3-642-17517-6_36</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Brimkov, V. E., Junosza-Szaniawski, K., Kafer, S., Kratochvíl, J., Pergel, M., Rzążewski, P., et al. (2018). Homothetic polygons and beyond: Maximal cliques in intersection graphs. Discrete Applied Mathematics, 247, 263–277. https://doi.org/10.1016/j.dam.2018.03.046 <a href="https://doi.org/10.1016/j.dam.2018.03.046" target="_blank">https://doi.org/10.1016/j.dam.2018.03.046</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Graphs with few cliques open-in-new

Graphs with few cliques