Fragments of algebraic graph theory

Fragments of algebraic graph theory

Date

Every week during three months from January to March, 2021.

Location 

We will offer the course partly or entirely virtually.

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.

Fragments of algebraic graph theory

Registration form

Date

Every week during three months from January to March, 2021.

Location

We will offer the course partly or entirely virtually

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.

Fragments of algebraic graph theory

Registration form

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

Share This