Jongyook Park (박종육), May 26, Tuesday, 6-7 PM, How much does local information determine a graph?
Keimyung Discrete Math Seminar (계명 이산수학 세미나)
Date and Time: May 26, Tuesday, 6-7 PM
Title : How much does local information determine a graph?
Speaker: Jongyook Park (박종육), Kyungpook National University (경북대학교)
Location: Room 324
Abstract: Strongly regular graphs are defined by very simple rules: every vertex has the same number of neighbors, and any two vertices share a fixed number of common neighbors. Surprisingly, these local conditions already impose strong restrictions on the global structure of the graph.
In this talk, we introduce the basic ideas of spectral graph theory, where graphs are studied using eigenvalues of matrices. We explain how eigenvalues capture global information, and how they can be used to detect hidden structure.
We also show that spectral information alone is not always sufficient, and introduce additional combinatorial methods involving cliques and cocliques. Using these tools, we present examples where certain graphs cannot exist, even though all known numerical conditions are satisfied.