Fragments of algebraic graph theory
Fragments of algebraic graph theory
Date
From January 13 to March 25, 2021, Wednesdays and Thursdays 17h-19h (Barcelona time)
Location
The course will be entirely accessible through the web.
Course Description:
This course will cover a variety of largely independent parts of algebraic graph theory. It is an intent to promote graphs to algebraists and algebraic tools to graph theorists. There will be classic results, famous open problems, and recent developments mostly from three big areas. The order is not precisely as below, but topics will also be mixed a bit. The sessions will be often independent, so selective presence is possible.
Format:
- 2-hour lectures, plus 2-hour progress reports on problems, experiments, and exercises. Every week during three months Jan 2021-Mar 2021.
- Participants form groups and attack exercises, new directions, and open problems together.
- We will offer the course partly or entirely virtually (and for a big audience).
- We aim at PhD students and fellow researchers.
- Only elementary notions of linear algebra and graph theory is required.
If you wish to attend the course, please contact kolja.knauer@ub.edu
Date
From January 13 to March 25, 2021, Wednesdays and Thursdays 17h-19h (Barcelona time)
Location
The course will be entirely accessible through the web.
Course Description:
This course will cover a variety of largely independent parts of algebraic graph theory. It is an intent to promote graphs to algebraists and algebraic tools to graph theorists. There will be classic results, famous open problems, and recent developments mostly from three big areas. The order is not precisely as below, but topics will also be mixed a bit. The sessions will be often independent, so selective presence is possible.
Format:
2H lectures, plus 2H progress reports on problems, experiments, and exercises. Every week during three months Jan 2021-Mar 2021.
Participants form groups and attack exercises, new directions, and open problems together.
We will offer the course partly or entirely virtually (and for a big audience).
We aim at PhD students and fellow researchers.
Only elementary notions of linear algebra and graph theory is required.
If you have any issues with the registration process, please contact secretariat@bgsmath.cat
Contents
N. Some first notions and a little linear algebra of the incidence matrix (KK, 1 week):
cycle space, minors, planarity, and Mac Lane’s planarity criterion.
I. Graphs and groups (KK, 4 weeks):
automorphism group and endomorphism monoid of a graph, transitivity and rigidity, Frucht-type results, Cayley graphs of groups and semigroups, retracts and contractions, Hamiltonicity, Lovasz’ conjecture, the characterization of planar groups, insensitivity, stability.
II. The linear algebra of the adjacency matrix (MAFM, 4 weeks):
Graph Spectrum: adjacency spectrum, Laplacian spectrum
Linear Algebra: Perron-Frobenius theory, equitable partitions, interlacing, Huang’s proof of the sensitivity conjecture
Eigenvalues and Eigenvectors: Cliques and cocliques, k-independence number, Shannon capacity and Lovasz theta number, Laplacian (Rone-Merris conjectures). Applications (Google page rank, cutting, graph drawing, clustering)
The second largest eigenvalues: Bounds, randomness, expansion, toughness & hamiltonicity, diameter bound
Distance-regular graphs: Algebraic and spectral characterizations, Bannai-Ito conjecture, strongly-regular graphs
III. Semidefinite bounds and approximations for NP-complete problems (JP, 4 weeks):
maximum cut, maximum induced matching, stable sets, graph partition, chromatic number;
applications to symmetric and regular graphs;
applications to spectral and algebraic graph theory