Sebastian M. Cioaba
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Sebastian M. Cioaba has a total of 103 co-authors. Here are the top co-authors by number of shared publications:
- Jack H. Koolen
School of Mathematical Sciences University of Science and Technology of China 230026 Hefei People's Republic of China
17 shared publications - M. Ram Murty
Department of Mathematics and Statistics, Queen’s University, Kingston, Canada
13 shared publications - Willem H. Haemers
Tilburg University The Netherlands
9 shared publications - Hiroshi Nozaki
Toyota Central Research and Development Laboratories (Japan)
6 shared publications David A. Gregory
Department of Mathematics Queen's University at Kingston Canada
4 shared publicationsMatt McGinnis
4 shared publications
Latest Publications
- Open Access
The non-existence of some Moore polygons and spectral Moore bounds
In this paper, we study the maximum order $v(k,θ)$ of a connected $k$-regular graph whose second largest eigenvalue is at most $θ$. From Alon-Boppana and Serre, we know that $v(k,θ)$ is finite when $θ< 2\sqrt{k-1}$ while the work of Marcus, Spielman, and Srivastava implies that $v(k,θ)$ is infinite if $θ\geq 2\sqrt{k-1}$. Cioabă, Koolen, Nozaki, and Vermette obtained a general upper bound on $v(k, θ)$ via Nozaki's linear programming bound and determined many values of $v(k,θ)$. The graphs attaining this bound are distance-regular and are called Moore polygons. Damerell and Georgiacodis proved that there are no Moore polygons of diameter $6$ or more. For smaller diameters, there are infinitely many Moore polygons. We complement these results by proving two nonexistence results for Moore polygons with specific parameters. We also determine new values of $v(k,θ)$: $v(4, \sqrt{2}) = 14$ and $v(5, \sqrt{2}) = v(5,\sqrt{5}-1)=16$. The former is achieved by the co-Heawood graph, and the latter by the folded $5$-cube. We verify that any connected $5$-regular graph with second eigenvalue $λ_2$ exceeding $1$ satisfies $λ_2 \geq \sqrt{5} - 1$, and that the unique $5$-regular graph attaining equality in this bound has $10$ vertices. We prove a stronger form of a 2015 conjecture of Kolokolnikov related to the second eigenvalue of cubic graphs of given order, and observe that other recent results on the second eigenvalue of regular graphs are consequences of the general upper bound theorem on $v(k,θ)$ mentioned above.Open AccessThe non-existence of some Moore polygons and spectral Moore bounds
In this paper, we study the maximum order $v(k,θ)$ of a connected $k$-regular graph whose second largest eigenvalue is at most $θ$. From Alon-Boppana and Serre, we know that $v(k,θ)$ is finite when $θ< 2\sqrt{k-1}$ while the work of Marcus, Spielman, and Srivastava implies that $v(k,θ)$ is infinite if $θ\geq 2\sqrt{k-1}$. Cioabă, Koolen, Nozaki, and Vermette obtained a general upper bound on $v(k, θ)$ via Nozaki's linear programming bound and determined many values of $v(k,θ)$. The graphs attaining this bound are distance-regular and are called Moore polygons. Damerell and Georgiacodis proved that there are no Moore polygons of diameter $6$ or more. For smaller diameters, there are infinitely many Moore polygons. We complement these results by proving two nonexistence results for Moore polygons with specific parameters. We also determine new values of $v(k,θ)$: $v(4, \sqrt{2}) = 14$ and $v(5, \sqrt{2}) = v(5,\sqrt{5}-1)=16$. The former is achieved by the co-Heawood graph, and the latter by the folded $5$-cube. We verify that any connected $5$-regular graph with second eigenvalue $λ_2$ exceeding $1$ satisfies $λ_2 \geq \sqrt{5} - 1$, and that the unique $5$-regular graph attaining equality in this bound has $10$ vertices. We prove a stronger form of a 2015 conjecture of Kolokolnikov related to the second eigenvalue of cubic graphs of given order, and observe that other recent results on the second eigenvalue of regular graphs are consequences of the general upper bound theorem on $v(k,θ)$ mentioned above. - 20 October 2025
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 730, 152-197
Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
- 20 October 2025
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 730, 152-197
Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
- Open Access
Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). In this paper, we investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this direction, we study the clique complexes of strongly regular graphs, and determine the spectra of the triangle complexes of several families of strongly regular graphs including Hamming graphs and Triangular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. We also prove that if a graph has the property that for any induced cycle, there are four consecutive vertices on the cycle with a common neighbor, then the first cohomology group of the graph is trivial and we apply this result to several families of graphs.
Open AccessClique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). In this paper, we investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this direction, we study the clique complexes of strongly regular graphs, and determine the spectra of the triangle complexes of several families of strongly regular graphs including Hamming graphs and Triangular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. We also prove that if a graph has the property that for any induced cycle, there are four consecutive vertices on the cycle with a common neighbor, then the first cohomology group of the graph is trivial and we apply this result to several families of graphs.
- Open Access
- 1 July 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (1)
The spectral even cycle problem
In this paper, we study the maximum adjacency spectral radii of graphs of large order that do not contain an even cycle of given length. For \(n›k\), let \(S_{n,k}\) be the join of a clique on \(k\) vertices with an independent set of \(n-k\) vertices and denote by \(S_{n,k}^+\) the graph obtained from \(S_{n,k}\) by adding one edge. In 2010, Nikiforov conjectured that for \(n\) large enough, the \(C_{2k+2}\)-free graph of maximum spectral radius is \(S_{n,k}^+\) and that the \(\{C_{2k+1},C_{2k+2}\}\)-free graph of maximum spectral radius is \(S_{n,k}\). We solve this two-part conjecture.Mathematics Subject Classifications: 05C35, 05C50Keywords: Spectral Turán number, even-cycle problem, Brualdi-Solheid problem- 1 July 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (1)
Open AccessThe spectral even cycle problem
In this paper, we study the maximum adjacency spectral radii of graphs of large order that do not contain an even cycle of given length. For \(n›k\), let \(S_{n,k}\) be the join of a clique on \(k\) vertices with an independent set of \(n-k\) vertices and denote by \(S_{n,k}^+\) the graph obtained from \(S_{n,k}\) by adding one edge. In 2010, Nikiforov conjectured that for \(n\) large enough, the \(C_{2k+2}\)-free graph of maximum spectral radius is \(S_{n,k}^+\) and that the \(\{C_{2k+1},C_{2k+2}\}\)-free graph of maximum spectral radius is \(S_{n,k}\). We solve this two-part conjecture.Mathematics Subject Classifications: 05C35, 05C50Keywords: Spectral Turán number, even-cycle problem, Brualdi-Solheid problem - Open Access
- 1 January 2024
- Published by Walter de Gruyter GmbH in Special Matrices
- Vol. 12 (1)
On the minimum spectral radius of connected graphs of given order and size
In this article, we study a question of Hong from 1993 related to the minimum spectral radii of the adjacency matrices of connected graphs of given order and size. Hong asked if it is true that among all connected graphs of given number of vertices and number of edges , the graphs having minimum spectral radius (the minimizer graphs) must be almost regular, meaning that the difference between their maximum degree and their minimum degree is at most one. In this article, we answer Hong’s question positively for various values of and , and in several cases, we determined the graphs with minimum spectral radius.- 1 January 2024
- Published by Walter de Gruyter GmbH in Special Matrices
- Vol. 12 (1)
Open AccessOn the minimum spectral radius of connected graphs of given order and size
In this article, we study a question of Hong from 1993 related to the minimum spectral radii of the adjacency matrices of connected graphs of given order and size. Hong asked if it is true that among all connected graphs of given number of vertices and number of edges , the graphs having minimum spectral radius (the minimizer graphs) must be almost regular, meaning that the difference between their maximum degree and their minimum degree is at most one. In this article, we answer Hong’s question positively for various values of and , and in several cases, we determined the graphs with minimum spectral radius. - 16 November 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 325, 212-225
The least Euclidean distortion constant of a distance-regular graph
- 16 November 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 325, 212-225
The least Euclidean distortion constant of a distance-regular graph
- Open Access
On the spectrum and linear programming bound for hypergraphs
The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander graphs. In this paper, we extend previous work done for graphs and bipartite graphs and present a linear programming method for obtaining an upper bound on the order of a regular uniform hypergraph with prescribed distinct eigenvalues. Furthermore, we obtain a general upper bound on the order of a regular uniform hypergraph whose second eigenvalue is bounded by a given value. Our results improve and extend previous work done by Feng-Li (1996) on Alon-Boppana theorems for regular hypergraphs and by Dinitz-Schapira-Shahaf (2020) on the Moore or degree-diameter problem. We also determine the largest order of an $r$-regular $u$-uniform hypergraph with second eigenvalue at most $\theta$ for several parameters $(r,u,\theta)$. In particular, orthogonal arrays give the structure of the largest hypergraphs with second eigenvalue at most $1$ for every sufficiently large $r$. Moreover, we show that a generalized Moore geometry has the largest spectral gap among all hypergraphs of that order and degree.Open AccessOn the spectrum and linear programming bound for hypergraphs
The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander graphs. In this paper, we extend previous work done for graphs and bipartite graphs and present a linear programming method for obtaining an upper bound on the order of a regular uniform hypergraph with prescribed distinct eigenvalues. Furthermore, we obtain a general upper bound on the order of a regular uniform hypergraph whose second eigenvalue is bounded by a given value. Our results improve and extend previous work done by Feng-Li (1996) on Alon-Boppana theorems for regular hypergraphs and by Dinitz-Schapira-Shahaf (2020) on the Moore or degree-diameter problem. We also determine the largest order of an $r$-regular $u$-uniform hypergraph with second eigenvalue at most $\theta$ for several parameters $(r,u,\theta)$. In particular, orthogonal arrays give the structure of the largest hypergraphs with second eigenvalue at most $1$ for every sufficiently large $r$. Moreover, we show that a generalized Moore geometry has the largest spectral gap among all hypergraphs of that order and degree. - 4 April 2022
- Published by Elsevier in European Journal of Combinatorics
- Vol. 104, 103535
On the spectrum and linear programming bound for hypergraphs
- 4 April 2022
- Published by Elsevier in European Journal of Combinatorics
- Vol. 104, 103535
On the spectrum and linear programming bound for hypergraphs
- 1 February 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (2) , 1-26
On the Eigenvalues of Grassmann Graphs, Bilinear Forms Graphs and Hermitian Forms Graphs
- 1 February 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (2) , 1-26
On the Eigenvalues of Grassmann Graphs, Bilinear Forms Graphs and Hermitian Forms Graphs
- 1 January 2022
- Published by Springer Nature
- p. 71-91
Möbius Inversion and Graph Colouring