Browsing by Author "Nasserasr, Shahla"

Now showing 1 - 3 of 3

Open Access
Extensions of the Erdős-Ko-Rado Theorem to Perfect Matchings
(Faculty of Graduate Studies and Research, University of Regina, 2022-03-31) Nasrollahi Shirazi, Mahsa; Meagher, Karen; Fallat, Shaun; Herman, Allen; Zilles, Sandra; Nasserasr, Shahla; Guo, Krystal
One of the important results in extremal set theory is the Erdős-Ko-Rado (EKR) theorem which gives a tight upper bound on the size of intersecting sets. The focus of this thesis is on extensions of the EKR theorem to perfect matchings and uniform set partitions. Two perfect matchings are said to be t-intersecting if they have at least t edges in common. In 2017, Godsil and Meagher algebraically proved the EKR theorem for intersecting perfect matchings on the complete graph with 2k vertices. In 2017, Lindzey presented an asymptotic refinement of the EKR theorem on perfect matchings. In this thesis, we extend their results to 2-intersecting and also to set-wise 2-intersecting perfect matchings. These results are not asymptotic. A perfect matching is in fact a special case of a uniform set partition. Another focus of this thesis is on partially 2-intersecting uniform set partitions. We find the largest set of 2-intersecting uniform set partitions, when the number of parts is sufficiently large. The result on uniform set partitions is part of a joint research project with Karen Meagher and Brett Stevens.
Open Access
Minimum number of distinct eigenvalues of graphs
(International Linear Algebra Society, 2013-09) Ahmadi, Bahman; Alinaghipour, Fatemeh; Cavers, Michael; Fallat, Shaun; Meagher, Karen; Nasserasr, Shahla
The minimum number of distinct eigenvalues, taken over all real symmetric matrices compatible with a given graph G, is denoted by q(G). Using other parameters related to G, bounds for q(G) are proven and then applied to deduce further properties of q(G). It is shown that there is a great number of graphs G for which q(G) = 2. For some families of graphs, such as the join of a graph with itself, complete bipartite graphs, and cycles, this minimum value is obtained. Moreover, examples of graphs G are provided to show that adding and deleting edges or vertices can dramatically change the value of q(G). Finally, the set of graphs G with q(G) near the number of vertices is shown to be a subset of known families of graphs with small maximum multiplicity.
Open Access
On the null space struture associted with trees and cycles
(The Charles Babbage Research Centre, 2013-02) Fallat, Shaun; Nasserasr, Shahla
In this work, we study the structure of the null spaces of matrices associated with graphs. Our primary tool is utilizing Schur complements based on certain collections of independent vertices. This idea is applied in the case of trees, and seems to represent a unifying theory within the context of the support of the null space. We extend this idea and apply it to describe the null vectors and corresponding nullities of certain symmetric matrices associated with cycles.