In mathematics, a clique is a group where everyone is connected to everyone else.
In short: In graph theory, a clique is a subset of vertices where every pair is directly connected. While the term originated from social network analysis to model groups of friends, it has become a fundamental tool in bioinformatics and computer science, despite the notorious difficulty of identifying them in complex networks.
At its core, a clique is a complete subgraph. If you visualize a graph as a collection of points connected by lines, a clique is a cluster where every single point has a direct line to every other point in that cluster. The concept was formalized by Luce and Perry in 1949, who borrowed the term from sociology to describe social circles where every member knows every other member. This structural definition remains a cornerstone of graph theory, providing a rigorous way to analyze interconnectedness.
The computational challenge of finding cliques is significant. The 'clique problem'—determining if a graph contains a clique of a specific size—is classified as NP-complete. This means that as the graph grows, the time required to solve the problem typically grows exponentially. Despite this, researchers have developed various algorithms, such as the Bron-Kerbosch method, to navigate this complexity. In specific graph families like perfect or planar graphs, the problem can be solved much more efficiently in polynomial time.
Beyond simple identification, cliques are essential for characterizing complex structures. For instance, a chordal graph is defined by a specific ordering of vertices that forces neighbors to form cliques, while a cluster graph is essentially a collection of disjoint cliques. Theoretical results like Turán's theorem provide bounds on how many edges a graph must have before a clique of a certain size is guaranteed to appear. These mathematical frameworks allow scientists to model everything from social dynamics to the intricate relationships within biological systems, proving that the simple idea of total connectivity is a powerful lens for understanding structure.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Clique (graph theory)
To cite this card, link to https://intellectplus.co.uk/app/science-clique-graph-theory.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics