Projects / Programmes
Distance-regular graphs: irreducible T-modules with endpoint 1 and action of the automorphism group
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
distance-regular graph, irreducible T-module, group action, automorphism group
Researchers (12)
Organisations (2)
Abstract
Our research concerns a combinatorial object known as a graph. A graph is a finite set of vertices, together with a set of undirected arcs or edges, each of which connects a pair of distinct vertices. We say that vertices x; y are adjacent whenever x; y are connected by an edge. The concept of a graph is useful because mathematical as well as intuitive notions can be formulated in terms of adjacency. In our research we study graphs which are called distance-regular. The 1-skeletons of the five platonic solids provide examples of distance-regular graphs. The theory of distance-regular graphs is connected to some other areas of mathematics, such as coding theory, representation theory, and the theory of orthogonal polynomials.
To describe main goals of our project, we first recall the definition of distance-regular graph. Let Γ = (X, R) denote a graph with vertex set X, edge set R, shortest-path distance function d, and diameter D. We say Γ is distance-regular whenever for all integers h, i, j (0 ≤ h, i, j ≤ D), and all vertices x, y of Γ with d(x, y) = h, the number of vertices, which are at distance i from x and at distance j from y, depends only on the numbers i, j, h (and not on the choice of vertices x, y).
Our project consists of two main parts: study of Terwilliger algebras of distance-regular graphs (via their irreducible modules), and study of group actions on distance-regular graphs. To describe our main goal in the first part of our project, let us recall the definition of Terwilliger algebra of Γ. Let Γ denote a distance-regular graph with diameter D and pick a vertex x of Γ. For 0 ≤ i ≤ D we define diagonal matrices E_i^*=E_i^*(x), which have columns and rows indexed by the vertices of Γ. For vertex y of Γ, the (y,y)-entry of E_i^* is 1, if d(x,y)=i, and 0 otherwise. Matrices E_i^* are called dual idempotents of Γ (with respect to x). Terwilliger algebra T=T(x) of Γ is the matrix algebra generated by the adjacency matrix of Γ and the dual idempotents of Γ. In the first part of our project, our central goal will be to solve the following problem.
Problem Let Γ be a distance-regular graph. Pick a vertex x of Γ and let T=T(x) denote the corresponding Terwilliger algebra. Assume that Γ has (up to isomorphism) exactly three irreducible T-modules with endpoint 1, and these T-modules are all thin. Find combinatorial consequences of this algebraic condition.
Two describe our main goal in the second part of our project, let us recall the definition of a Cayley graph. Let H denote a finite group and let S be a generating subset of H, which is inverse-closed and which does not contain the identity element of H. A Cayley graph of a group H with respect to the set of generators S, denoted by Cay(H; S), is the
graph with vertex-set H, where element x of H is adjacent to element y of H whenever the product of x and the inverse element of y is contained in S. In the second part of our project, our main goal will be to solve the following problem.
Problem For certain classes of groups H, determine all distance-regular graphs, which are Cayley graphs on a group in H. In particular, we will try to solve this problem for groups which are direct products of two cyclic groups (at least for some particular choices of orders of these cyclic groups) and for generalized dihedral groups.
In the course of the project we will try to solve number of other problems which are related to the above described main problems of the project.
Significance for science
One of the core concepts essential to understanding natural phenomena and the dynamics of social systems is the concept of “relation”. Human friendships, social and interconnection networks, traffic systems, chemical structures, etc. can be expressed as relational structures. Furthermore, scientists rely on relational structures with high levels of symmetry because of their optimal behavior and high performance. A mathematical model capturing the essence of this situation is a graph exhibiting a high level of symmetry, and the underlying mathematical discipline is algebraic graph theory which is the discipline considered in this proposal. Algebraic graph theory is a part of discrete mathematics involving a wide range of methods from combinatorics, linear algebra, permutation groups, group representations, association schemes, algorithms, geometry, topology, etc. While some symmetries are obvious, certain additional symmetries remain hidden or difficult to grasp. Knowing the full (or as near as possible) set of symmetries of an object is important because it provides the most complete description of that object's structure.
Mathematics has been called the “invisible oil” which keeps our technological society running efficiently. There is a common misunderstanding that technology has solved all our problems. For example, that the availability of powerful computer packages means that users do not require mathematical skills. This is simply untrue. More mathematically and statistically trained young people are needed to use new technology successfully and efficiently. The proposed project is going to spread this message effectively.
Significance for the country
One of the core concepts essential to understanding natural phenomena and the dynamics of social systems is the concept of “relation”. Human friendships, social and interconnection networks, traffic systems, chemical structures, etc. can be expressed as relational structures. Furthermore, scientists rely on relational structures with high levels of symmetry because of their optimal behavior and high performance. A mathematical model capturing the essence of this situation is a graph exhibiting a high level of symmetry, and the underlying mathematical discipline is algebraic graph theory which is the discipline considered in this proposal. Algebraic graph theory is a part of discrete mathematics involving a wide range of methods from combinatorics, linear algebra, permutation groups, group representations, association schemes, algorithms, geometry, topology, etc. While some symmetries are obvious, certain additional symmetries remain hidden or difficult to grasp. Knowing the full (or as near as possible) set of symmetries of an object is important because it provides the most complete description of that object's structure.
Mathematics has been called the “invisible oil” which keeps our technological society running efficiently. There is a common misunderstanding that technology has solved all our problems. For example, that the availability of powerful computer packages means that users do not require mathematical skills. This is simply untrue. More mathematically and statistically trained young people are needed to use new technology successfully and efficiently. The proposed project is going to spread this message effectively.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
Interim report
