Applying algebra to computing the clique number of a graph

图中的团是指一个顶点的集合，该集合中每对不同的顶点都由一条边连接，图的团数是该图中最大团的大小。能够确定图的团数有许多应用，但在计算上是一个困难的问题。代数可以在确定或界定团数方面有很大的帮助，包括线性代数和特征值技术，具有某些正则性质的图类的团邻接多项式，如果图具有非平凡对称性，则群论。差距系统的GRAPE包包含了对具有给定属性的团进行分类的函数，这些函数对于具有大型对称群的图特别强大。作为这一领域任何项目的一部分，学生可以从计算GRAPE格式的有趣图形的广泛目录开始，用于形成和测试图形，并测试新的算法思想和程序。这样一个图书馆将是一个巨大的资源，无论是国际代数图论社区。

A clique in a graph is a set of vertices with the property that every pair of distinct vertices in the set is joined by an edge, and the clique number of a graph is the size of a largest clique in that graph. Being able to determine the clique number of a graph has many applications, but is a computationally difficult problem. Algebra can be a big help in determining or bounding the clique number, including linear algebra and eigenvalue techniques, the clique adjacency polynomial for classes of graphs with certain regularity properties, and if the graph has nontrivial symmetries, group theory. The GRAPE package for the GAP system contains functions for the classification of cliques with given properties, and these are especially powerful for graphs with large groups of symmetries. As part of any project in this area, a student could start by computing an extensive catalogue of interesting graphs in GRAPE format for use in forming and testing conjectures and for testing new algorithmic ideas and programs. Such a library would be a tremendous resource both for the international algebraic graph theory community.