Réunion d'hiver SMC 2024

Vancouver/Richmond, 29 novembre - 2 decembre 2024

Théorie algébrique des graphes I
Org: Sooyeong Kim (University of Guelph), Sarobidy Razafimahatratra (Fields Institute) et Harmony Zhan (Worcester Polytechnic Institute)
[PDF]

HIMANSHU GUPTA, University of Regina Minimum number of distinct eigenvalues of Johnson and Hamming graphs [PDF]

This talk focuses on the inverse eigenvalue problems for graphs (IEPG), which investigates the possible spectra of real symmetric matrices associated with a graph $G$. These matrices have off-diagonal non-zero entries corresponding to the edges of $G$, while diagonal entries are unrestricted. A key parameter in IEPG is $q(G)$, the minimum number of distinct eigenvalues among such matrices. We present lower bounds on $q(G)$ based on the existence or non-existence of certain cycles in $G$. Notably, we show that every Johnson graph admits a $\{-1,0,1\}$-matrix with exactly two distinct eigenvalues. Additionally, we explore $q(G)$ for Hamming graphs and other distance-regular graphs. This work is in collaboration with Shaun Fallat, Allen Herman, and Johnna Parenteau.

ALLEN HERMAN, University of Regina Parameters of quotient-polynomial graphs [PDF]

It is well-known that the parameters of a distance-regular graph (DRG) are determined by its intersection array. The intersection array is a minimal collection of intersection numbers that completely determines the intersection matrices of the association scheme determined by the DRG, and the adjacency algebra of this scheme is naturally polynomial in the adjacency matrix $A_1$ of the DRG. $\\$

It has been observed that many other symmetric association schemes are ``polynomial'' in the sense that their adjacency algebra is generated by the adjacency matrix of one of the graphs in the scheme. In a 2016 paper, Miguel Fiol referred to these graphs as quotient-polynomial graphs (QPGs). In 2023, a result of Xia, Tan, Liang, and Koolen showed that Q-polynomial association schemes are generated by the adjacency matrix of a QPG. $\\$

Earlier this year, Roghayeh Maleki and I released a database of parameters of QPGs whose association schemes are polynomial in $A_1$, where $A_1$ is the adjacency matrix of the QPG. We show each such QPG determines an equivalence class of QPG-parameter arrays, and the intersection matrices of the corresponding association scheme are determined by the QPG-parameter array. $\\$

In this talk I will explain how to work with QPG-parameter arrays, the techniques used to generate this database, and discuss the feasibility and realizability tests we have developed for QPG-parameter arrays. This is joint work with Roghayeh Maleki.

KUMAR HITESH, Simon Fraser University Combinations of first and second eigenvalue of trees [PDF]

For an $n$-vertex graph $G$, let $\lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G)$ denote the eigenvalues of its adjacency matrix. In this talk, the speaker will present results concerning the extremization of combinations of $\lambda_1$ and $\lambda_2$ in the class of trees. These results are part of an ongoing project with Bojan Mohar, Shivaramakrishna Pragada, and Hanmeng Zhan.

LORD KAVI, Concordia University of Edmonton Towards Haemers Laplacian Toughness Conjecture [PDF]

This talk focuses on graph connectivity and toughness, highlighting an improved bound on vertex connectivity as initially proposed by Krivelevich and Sudakov. Toughness, introduced by Chvátal in 1973, is a key measure of how well different parts of a graph are connected, with implications for Hamiltonicity, spanning trees, connectivity, and more. We derive new bounds on graph toughness and confirm specific cases of a Laplacian-based toughness conjecture by Haemers. Our results include confirmations for regular bipartite graphs, trees, graphs with at least one leaf, graphs with up to 8 vertices, and some specially constructed examples.

THEDORE KOLOKOLNIKOV, Dalhousie University Maximizing network connectivity subject to resource constraints [PDF]

One way to measure how fast the network can propagate the information is using the Algebraic Connectivity (AC, or spectral gap) of a graph, which corresponds to the second eigenvalue of the Laplacian of the graph. We address the following question. Among all graphs of a given number of nodes n and edges m, which graph maximizes the AC? Generally, this question is very difficult for all but very small n and m (e.g. n=20, m=30).

For regular graphs, we derive attainable upper bounds on AC in terms of diameter and girth. Our diameter bound agrees with the well-known Alon-Boppana-Friedman bound for graphs of even diameter, but is an improvement for graphs of odd diameter. We then use a combination of stochastic algorithms and exhaustive search to find graphs which attain the diameter bound. For 3-regular graphs, we find attainable graphs for all diameters D up to and including D = 9 (the case of D = 10 is open). These graphs are extremely rare and also have high girth; for example we found exactly 45 distinct cubic graphs on 44 vertices attaining the upper bound when D = 7; all had girth 8 (out of a total of 266362 girth-8 graphs on 44 vertices).

We also derive an asymptotic bound for AC for several classes of random semi-regular graphs. In particular, we show that certain semi-regular graphs of average degree $d<8$ are better than regular graphs of the same average degree, but regular graphs win when $d\ge8$.

JINTING LIANG, UBC Log-concavity and log-convexity via distributive lattices [PDF]

In this work we present a lemma, which we call the Order Ideal Lemma, that can be used to demonstrate a wide array of log-concavity and log-convexity results in a combinatorial manner using order ideals in distributive lattices. We use the Order Ideal Lemma to prove log-concavity and log-convexity of various sequences involving lattice paths (Catalan, Motzkin and large Schr\"oder numbers), intervals in Young's lattice, order polynomials, specializations of Schur and Schur $Q$-functions, Lucas sequences, descent and peak polynomials of permutations, pattern avoidance, set partitions, and noncrossing partitions. This is a joint work with Bruce E. Sagan.

BOJAN MOHAR, Simon Fraser University Square energy of graphs [PDF]

Let $G$ be a graph of order $n$ with eigenvalues $\lambda_1 \geq \cdots \geq\lambda_n$. Let \[s^+(G)=\sum_{\lambda_i>0} \lambda_i^2, \qquad s^-(G)=\sum_{\lambda_i<0} \lambda_i^2.\] The smaller value, $s(G)=\min\{s^+(G), s^-(G)\}$ is called the square energy of $G$. In 2016, Elphick, Farber, Goldberg, and Wocjan conjectured that for every connected graph $G$ of order $n$, $s(G)\geq n-1$. The bound is attained for any tree and also for every complete graph. No linear lower bound for $s(G)$ in terms of $n$ is known. The speaker will prove that $s(G)\geq \frac{3n}{4}$ for every connected graph $G$ of order $n\ge 4$. This is joint work with Saieed Akbari, Hitesh Kumar, and Shivaramakrishna Pragada.

SHIVARAM PRAGADA, SIMON FRASER UNIVERSITY Bollobas-Nikiforov conjecture and triangle counting [PDF]

Let $G$ be a graph with $n$ vertices. Let $A(G)$ be its adjacency matrix. Let $\lambda_1(G), \lambda_2(G)$ denote the largest and second largest eigenvalues of the adjacency matrix. Bollob\'{a}s and Nikiforov (2007) conjectured that for any graph $G \neq K_n$ with $m$ edges \[\lambda_1^2+\lambda_2^2\le \bigg( 1-\frac{1}{\omega(G)}\bigg)2m\] where $\omega(G)$ denotes the clique number of $G$. In this talk, we prove this conjecture for graphs with not so many triangles, using the method of triangle counting. This is a joint work with Hitesh Kumar.

SAROBIDY RAZAFIMAHATRATRA, Fields Institute The intersection density of transitive groups of degree $3p$ [PDF]

Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a subset $\mathcal{F}\subset G$ is intersecting if for any $g,h\in G$, there exists $\omega\in \Omega$ such that $\omega^g = \omega^h$. The intersection density of $G$ is the rational number \begin{align*} \rho(G):= \max \left\{ \frac{|\mathcal{F}|}{|G|/|\Omega|} : \mathcal{F} \subset G \mbox{ is intersecting} \right\}. \end{align*}

In 2022, Meagher asked whether $\rho(G) \in \left\{1,\frac{3}{2},3\right\}$ for any transitive group $G\leq \operatorname{Sym}(\Omega)$ of degree $|\Omega| = 3p$, where $p\geq 5$ is an odd prime. Except for the cases where $p=q+1$ is a Fermat prime and $\Omega$ admits a unique $G$-invariant partition $\mathcal{B}$, whose blocks are of size $3$, such that the induced action of $G$ on $\mathcal{B}$ is isomorphic to $\operatorname{PSL}_2(q)$, I will answer Meagher's question positively for imprimitive groups admitting a normal block system.

Joint work with Roghayeh Maleki.

KIM SOOYEONG, University of guelph Perfect state transfer in a graph and its line graph [PDF]

In the study of continuous quantum walks on graphs, perfect state transfer between $\mathbf{x}$ and $\mathbf{y}$ has been well-explored when $\mathbf{x}$ and $\mathbf{y}$ are standard basis vectors, specifically $\mathbf{e}_v$ and $\mathbf{e}_w$ corresponding to vertices $v$ and $w$. Chen and Chris extended this by investigating cases where $\mathbf{x} = \mathbf{e}_a \pm \mathbf{e}_b$ and $\mathbf{y} = \mathbf{e}_c \pm \mathbf{e}_d$.

This led us to a graph-theoretic question: Given a graph $G$ that permits perfect state transfer between $\mathbf{e}_a + \mathbf{e}_b$ and $\mathbf{e}_c + \mathbf{e}_d$ for edges $\{a,b\}$ and $\{c,d\}$, does its line graph $\ell(G)$ also exhibit perfect state transfer between $\mathbf{e}_v$ and $\mathbf{e}_w$, where $v$ and $w$ correspond to the edges $\{a,b\}$ and $\{c,d\}$, respectively? Moreover, is the converse true? We will address this question and provide relevant examples.

THOMÁS SPIER, University of Waterloo Efficient reconstruction of the characteristic polynomial [PDF]

It was proved by Hagos that, for every graph $G$, the pair of characteristic polynomials $(\phi^G, \phi^{\overline{G}})$ is reconstructible from the pairs $(\phi^{G\setminus i}, \phi^{\overline{G}\setminus i})$ for $i$ in $V(G)$. In this talk, we present an efficient algorithm that reconstructs $(\phi^G, \phi^{\overline{G}})$ and some related results.

haut de la page