Applying algebra to computing the clique number of a graph
Lead Research Organisation:
Queen Mary University of London
Department Name: Sch of Mathematical Sciences
Abstract
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.
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.
People |
ORCID iD |
| Leonard Soicher (Primary Supervisor) | |
| Rhys Evans (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N50953X/1 | 01/10/2016 | 30/09/2021 | |||
| 1791058 | Studentship | EP/N50953X/1 | 01/10/2016 | 31/03/2020 | Rhys Evans |
| Description | A graph from the class of strongly regular graphs is defined to have certain regularity properties. This class of graphs has been studied extensively, and there are many open theoretical and computational problems involving strongly regular graphs. I have collected a library of strongly regular graphs with relatively small order, and made them available in a format that can be loaded into the computational discrete algebra system, GAP. Using this, I have been able to verify or disprove known conjectures. Along with this library I have also developed functionality for the investigation of a graphs regularity and algebraic properties. Both this new functionality and the library is made available to the wider research community through its release as a GAP package called AGT (Algebraic Graph Theory). Greaves and Soicher use strongly regular graphs to compare clique bounds derived from eigenvalue techniques and Block Intersection Polynomials. I generalise their results to bounds on regular subgraphs in strongly regular graphs. I find that the Block Intersection Polynomial bound is at least as good as the eigenvalue bounds, and is strictly better for many graphs. Another interesting class of graphs which contains strongly regular graphs are edge-regular graphs. In the 1980s, Neumaier asked if there exists an edge-regular graph which is not strongly regular and containing a regular clique. Recently, two familiies of graphs with these properties are given by Greaves and Koolen. We give two further families of these graphs which have many different properties than the previously known examples. With these graphs, we answer questions posed by Greaves and Koolen. We also find several sufficient conditions for and edge-regular graph to be strongly regular, and characterised these in certain cases. We examine partitions of the Johnson graphs of diameter 3 into two regular induced subgraphs. The Johnson graphs are a very important family of distance regular graphs, with many connections to combinatorial designs and codes. We use the known combinatorial structure and algebraic proerties of the Johnson graphs to investigate the local structure of particular partitions. This builds on work which attempts to classify all partitions into two regualr induced subgraphs of the Johnson graphs of diameter 3. |
| Exploitation Route | The library of strongly regular graphs has already been used for testing conjectures and finding graphs with certain regularity or algebraic properties. The AGT package is now available to the wider research community, providing a resource for interesting examples of graphs and enable many to form questions based on the data available. I will continue to develop the functionality of this package and to make it useful to other researchers. After observing several constructions of strictly Neuamier graphs, interest in the possible algebraic and combinatorial properties of Neumaier graphs has emerged. One of the major open problems in this area is to determine the existence of a strictly Neumaier graph containing an m-regular clique, for every integer m>0. For this, I hope to use a computational approach to develop a better understanding of the problem, and give us some small examples of graphs with the properties we are looking for. Block intersection polynomials are a useful tool to use in searching for certain equitable partitions in regular graphs. The polynomials can be use to prove the nonexistence of partitions in specified graphs, or find further restrictions on the structure of a graph with such partitions. There is much interest in classifying equitable partitions of classes of graphs with known parameters, and these polynomials could be used to help in these cases. |
| Sectors | Other |
| URL | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p29;https://arxiv.org/abs/1809.03417;https://gap-packages.github.io/agt/ |
| Description | Algebra group travel funds: G2R2 |
| Amount | £500 (GBP) |
| Organisation | Queen Mary University of London |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 08/2018 |
| End | 08/2018 |
| Description | Algebra group travel funds: GAP |
| Amount | £250 (GBP) |
| Organisation | Queen Mary University of London |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 10/2016 |
| End | 10/2016 |
| Description | Algebra group travel funds: NATCOR |
| Amount | £250 (GBP) |
| Organisation | Queen Mary University of London |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 09/2017 |
| End | 09/2017 |
| Description | CoDiMa |
| Amount | £250 (GBP) |
| Organisation | University of St Andrews |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 03/2020 |
| End | 03/2020 |
| Description | CoDiMa |
| Amount | £270 (GBP) |
| Organisation | University of St Andrews |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 02/2020 |
| End | 02/2020 |
| Description | CoDiMa travel/accommodation support |
| Amount | £80 (GBP) |
| Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
| Sector | Public |
| Country | United Kingdom |
| Start | 10/2016 |
| End | 10/2016 |
| Description | Dr. Goryainov visit: May 2018 |
| Amount | £500 (GBP) |
| Organisation | Shanghai Jiao Tong University |
| Sector | Academic/University |
| Country | China |
| Start | 05/2018 |
| End | 05/2018 |
| Description | G2D2 travel funds |
| Amount | £600 (GBP) |
| Organisation | Shanghai Jiao Tong University |
| Sector | Academic/University |
| Country | China |
| Start | 08/2019 |
| End | 08/2019 |
| Description | G2R2 conference/summer school studentship |
| Amount | £275 (GBP) |
| Organisation | Novosibirsk State University |
| Sector | Academic/University |
| Country | Russian Federation |
| Start | 08/2018 |
| End | 08/2018 |
| Description | NATCOR course fees/accommodation |
| Amount | £300 (GBP) |
| Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
| Sector | Public |
| Country | United Kingdom |
| Start | 09/2017 |
| End | 09/2017 |
| Description | Russian Foundation for Basic Research (RFBR) research project ("Mobility") |
| Amount | 720,000 ₽ (RUB) |
| Funding ID | 19-31-50045 |
| Organisation | Russian Foundation for Basic Research |
| Sector | Academic/University |
| Country | Russian Federation |
| Start | 04/2020 |
| End | 10/2020 |
| Title | The AGT package for GAP |
| Description | A software package with functionality for hte investigation of graphs. Includes a large collection of strongly regular graphs on at most 40 vertices. Used in GAP computational software. |
| Type Of Material | Database/Collection of data |
| Year Produced | 2020 |
| Provided To Others? | Yes |
| Impact | Verification of conjecture stated by senior researchers. Have confirmed that for all possible strongly regular graph parameters (v,k,l,m) such the 2k |
| URL | https://gap-packages.github.io/agt/ |
| Description | The smallest strictly Neumaier graph and its generalisations |
| Organisation | Shanghai Jiao Tong University |
| Department | Exercise, Health and Technology Center |
| Country | China |
| Sector | Academic/University |
| PI Contribution | Collaborated on paper 'The smallest strictly Neumaier graph and its generalisations'. All authors input to the completed paper. |
| Collaborator Contribution | Collaborated on paper 'The smallest strictly Neumaier graph and its generalisations'. All authors input to the completed paper. Dr. Sergey Goryainov hosted me in Shanghai Jiao Tong University, through his personal funding. Further work also planned. |
| Impact | Collaborated on paper 'The smallest strictly Neumaier graph and its generalisations'. |
| Start Year | 2017 |
| Title | The AGT package for GAP |
| Description | The AGT package provides functionality to inspect combinatorial and algebraic properties of graphs in GRAPE format. It also provides a library strongly regular graphs on at most 40 vertices, and several graph constructions. |
| Type Of Technology | Software |
| Year Produced | 2020 |
| Open Source License? | Yes |
| Impact | Verification of conjecture stated by senior researchers. Have confirmed that for all possible strongly regular graph parameters (v,k,l,m) such the 2k |
| URL | https://gap-packages.github.io/agt/ |
| Description | Combinatorics study group seminar talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | National |
| Primary Audience | Professional Practitioners |
| Results and Impact | Seminar talk about strictly Neumaier graphs. Open problems discussed. |
| Year(s) Of Engagement Activity | 2018 |
| URL | https://www.qmul.ac.uk/maths/research/seminars/combinatorics-study-group/# |
| Description | G2D2 Conference talk 'Bounds for regular induced subgraphs of strongly regular graphs' |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | Presentation on 'Bounds for regular induced subgraphs of strongly regular graphs' given to conference/ summer school attendees. Further collaboration, networking and questions raised after talk. |
| Year(s) Of Engagement Activity | 2019 |
| URL | http://math.sjtu.edu.cn/conference/G2D2/index.html |
| Description | G2R2 Conference talk 'Neumaier graphs |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | Presentation on 'Neumaier graphs' given to conference/ summer school attendees. Further collaboration, networking and questions raised after talk. |
| Year(s) Of Engagement Activity | 2018 |
| URL | http://math.nsc.ru/conference/g2/g2r2/ |
| Description | PGR seminar talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Postgraduate students |
| Results and Impact | Seminar talk given about regular regular subgraphs. Open problems discussed. |
| Year(s) Of Engagement Activity | 2018 |
| URL | https://www.qmul.ac.uk/maths/research/seminars/queen-mary-internal-postgraduate-seminar/ |
| Description | Poster presentation on Neumaier graphs |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Postgraduate students |
| Results and Impact | Presented findings on Neumaier graphs with poster. Further discussions on problems discussed. |
| Year(s) Of Engagement Activity | 2018 |
| Description | USTC Seminar talk 'Neumaier graphs' |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | Seimnar talk 'Neumaier graphs' given. Further discussions, collaborations and problems discussed afterwards. |
| Year(s) Of Engagement Activity | 2018 |