Timezone: »

 
Graph neural networks for Ramsey graphs
Amur Ghose · Amit Levi · Yingxueff Zhang

@
in MATH-AI: Toward Human-Level Mathematical Reasoning »

Ramsey-like problems are ubiquitous in extremal combinatorics and occupy a central place in the field. In simple terms, Ramsey theory wishes to find the minimum size of a large graph structure such that some sought substructure - generally a clique or an independent set - is guaranteed to exist. Due to considerations of computational complexity, brute force approaches to solving these problems are usually not very feasible, as the substructures cannot be checked in polynomial time. At the same time, we seek extremal graphs that completely avoid such substructures to better understand the graph theory governing their occurrence. We investigate the feasibility of Graph Neural Networks (GNNs) in terms of indicating and refining search procedures for finding these special classes of Ramsey-extremal graphs, which are of interest to mathematicians.

[ Poster] 

Author Information

Amur Ghose (University of Waterloo)

I graduated from the Indian Inst. of Technology, Kanpur in 2018 and moved to UWaterloo for a master's.

Amit Levi (University of Waterloo)
Yingxueff Zhang (Huawei Technology Canada)

More from the Same Authors