Browsing by Author "Meagher, Karen"

Now showing 1 - 20 of 31

Open Access
C.V.
(2014-01-21) Meagher, Karen
Open Access
Calculating and Preserving Star Sets and Star Complements of General Matrices
(Faculty of Graduate Studies and Research, University of Regina, 2017-08-18) Bergen, Ryan Paul; Fallat, Shaun; Meagher, Karen; Hoeber, Orland
This thesis presents several results relating to star sets and star complements of graphs. While a method for calculating star sets and star complements involving pro- jection matrices has been known since their introduction, a second method involving determinants is demonstrated and shown to be equivalent to the rst method. Some of the theory for star sets and star complements is expanded to general diagonalizable matrices, regardless of symmetry. The concept of preserving star sets between two general matrices is introduced and shown to be an equivalence relation, and attempts are made to classify what types of matrices can preserve the star sets of a general matrix. Finally, we determine some results for general matrices that occur when star set preservation overlaps with other equivalence relations.
Open Access
Cameron-Liebler Sets for 2-Transitive Groups
(Faculty of Graduate Studies and Research, University of Regina, 2020-11) Palmarin, Daniel Michael; Fallat, Shaun; Meagher, Karen; Herman, Allen; Butz, Cortney
This research was conducted on 2-transitive groups whose minimal normal subgroup is abelian. Suppose G is such a group and ΓG is its derangement graph. Any maximum coclique S of ΓG has a characteristic vector xS. Each xS is a boolean vector contained in a particular module, which is called the permutation module MP. This module has a dimension of 1 + (n − 1)2, where n = deg(G), and it is spanned by {xij | i,j∈{1,...,n}}, where each xij is the characteristic vector of Sij, the set of permutations that map i to j. Apart from the xij, which correspond to the stabilizers of G and their cosets, this research set out to find any other boolean vectors that are contained in Mp using linear programming. Henceforth, such boolean vectors are defined to be Cameron-Liebler sets for 2-transitive groups. In addition to finding Cameron-Liebler sets, analyses were performed on each group to determine: (1) whether the strict EKR property holds; (2) the number of maximum cocliques that are subgroups, cosets, or neither; (3) isomorphism classes and conjugacy classes of the maximum cocliques that are subgroups; (4) the dimension of C′, the maximum cliques that are subgroups (along with their right cosets), and C, all maximum cliques; and (5) the spectrum of ΓG and whether the ratio bound is satisfied with equality.
Open Access
Cliques in block graphs of designs and orthogonal arrays
(Faculty of Graduate Studies and Research, University of Regina, 2024-03) Evans, Rachel Anne; Meagher, Karen; Kozdron, Michael; Pantangi, Venkata Raghu Tej
The Erdos-Ko-Rado [EKR] Theorem for intersecting families is a fundamental result in combinatorics, particularly in extremal set theory. This theorem not only establishes an upper bound on the size of the largest intersecting family but also characterizes the families that attain this bound—–these are known as maximal canonically intersecting. Recent work by Balogh, Das, Delcourt, Liu, and Sharifzadeh delves into intersecting families across permutations, hypergraphs, and vector spaces, revealing that nearly all such families within these structures are a subset of a maximal canonically intersecting family [1]. Building on these insights, this thesis extends the examination to block graphs of designs and orthogonal arrays. Through a comprehensive analysis of intersecting families within designs, we introduce a ratio between canonically intersecting families and non-canonical ones, demonstrating that almost all intersecting families in designs are canonical. This method, adaptable to orthogonal arrays OA(m, n) for sufficiently large n, is complemented by a conjecture proposing a second proof inspired by the methods given by Balogh et al. Notably, these results exclude symmetric and affine designs.
Open Access
The cyclotomic eigenvalue and character value problems for association schemes
(Faculty of Graduate Studies and Research, University of Regina, 2022-08) Maleki, Roghayeh; Allen, Herman; Meagher, Karen; Frankland, Martin; Yao, Yiyu; Martin, William J.
The central focus of this dissertation is an answer to the cyclotomic eigenvalue question (CEQ) for commutative association schemes. This question, which was posed by Simon Norton at Oberwolfach in 1980, asks whether all entries of the character table of a commutative association scheme lie in a cyclotomic extension of the rational numbers. In this thesis, we consider the cyclotomic eigenvalue question for objects that generalize the notion of association schemes. The objects in question are standard integral table algebras with integral multiplicities (SITAwIMs). Our main results show the eigenvalues of SITAwIMs of rank 4 and nonsymmetric ones of rank 5 are cyclotomic. This implies that the CEQ is affirmative for association schemes of rank 4 and nonsymmetric association schemes of rank 5. Moreover, for rank 5 symmetric SITAwIMs we give several examples that have noncyclotomic eigenvalues, and show the parameters for many of these examples satisfy all known parameter requirements for association schemes. Next, we provide an algorithm for computing fusions of a based algebra (A;B). We apply this algorithm to three problems: (1) computing fusion lattices for association schemes,of order up to 30; (2) realizing association schemes with transitive automorphism groups; (3) producing small examples of non-Schurian association schemes with noncyclotomic eigenvalues. We give an example of a group of order 96 for which two of its Schurian association scheme quotients have non-Schurian fusions with noncyclotomic eigenvalues. The latter is of interest to the open question asking whether association schemes with transitive automorphism groups can have noncyclotomic character values.
Open Access
Eigenvalues of K-Uniform Hypergraphs
(Faculty of Graduate Studies and Research, University of Regina, 2017-08) Gorr, Adam Vernon; Meagher, Karen; Fallat, Shaun; Herman, Allen; Gosselin, Shonda; Butz, Cory
We de ne two separate attempts to generalize the de nition of eigenvalues to hypergraphs and show several results related to each. The rst approach is rooted in 2-dimensional matrices and allows for the generalization of many results from graph theory. The second approach covered is more sophisticated and may only be applied to k-uniform hypergraphs. We include the development of a sound algorithm using the resultant of polynomials that can be used for any k-uniform hypergraph. Speci c examples are provided to demonstrate the power of the algorithm. Further, we show that certain results hold for the eigenvalues and associated eigenvectors of k-uniform hypergraphs and those hypergraphs obtained from combinatorial designs such as Steiner triple systems.
Open Access
Equivariant LS-Category and Equivariant Topological Complexity
(Faculty of Graduate Studies and Research, University of Regina, 2016-05) Bayeh, Marzieh; Stanley, Donald; Meagher, Karen; Gilligan, Bruce; Herman, Allen; Yao, Yiyu; Oprea, John
In this thesis we consider topological spaces endowed with an action of a topological group, and we develop a new concept to study these spaces. This concept is called orbit class and is often a good replacement for the well-known concept or- bit type. Using the concept of orbit class, we de ne a partial ordering on the set of all orbit classes. This partial order not only gives a partition on the topological space based on the orbits, but it also gives a discrete combinatorial translation of the topological space. We also use the properties of the orbit class to study equivariant LS-category and equivariant topological complexity. Equivariant LS-category was introduced by Marzantowicz in 1989, as a generalization of LS-category. Since then, equivariant LS-category has been studied by mathematicians and many results with di erent conditions have been developed. Equivariant topological complexity was introduced by Colman and Grant in 2012, as a generalization of topological complexity. In 2015, Lubawski and Marzantowicz introduced the invariant topological complexity as another generalization of the topological complexity and they claimed that their proposed invariant is more e cient than the equivariant topological complexity. In this thesis we study the equivariant LS-category and give some new results found by applying the properties of orbit class. We also study both the equivariant topological complexity and the invariant topological complexity. By using results from orbit class we show that in most cases the invariant topological complexity is in nite. In particular, if a topological space has more than one minimal orbit class then the invariant topological complexity is in nite. Finally, we study some particular cases of locally standard torus manifolds, and calculate their LS-category, topological complexity, equivariant LS-category, and invariant topological complexity. We also give counterexamples to two theorems from a published paper by Colman and Grant [10], and prove a modi ed version of one of those theorems.
Open Access
An Erdős-Ko-Rado theorem for finite \(2\)-transitive groups
(European Journal of Combinatorics, 2016) Meagher, Karen; Spiga, Pablo; Tiep, Pham Huu
We prove an analogue of the classical Erdős-Ko-Rado theorem for intersecting sets of permutations in finite \(2\)-transitive groups. Given a finite group \(G\) acting faithfully and \(2\)-transitively on the set \(\Omega\), we show that an intersecting set of maximal size in \(G\) has cardinality \(|G|/|\Omega|\). This generalises and gives a unifying proof of some similar recent results in the literature.
Open Access
The Erdős-Ko-Rado Theorem for intersecting families of permutations.
(Faculty of Graduate Studies and Research, University of Regina, 2010) Purdy, Alison May; Meagher, Karen; Fallat, Shaun; Zilles, Sandra
The Erdős-Ko-Rado Theorem is a fundamental result in extremal set theory. It describes the size and structure of the largest collection of subsets of size k from a set of size n having the property that any two subsets have at least t elements in common. Following the publication of the original theorem in 1961, many different proofs and extensions have appeared, culminating in the publication of the Complete Erdős-Ko-Rado Theorem by Ahlswede and Khachatrian in 1997. A number of similar results for families of permutations have appeared. These include proofs of the size and structure of the largest family of permutations having the property that any two permutations in the family agree on at least one element of the underlying set. In this thesis we apply techniques used in the proof of the Complete Erdős-Ko-Rado Theorem for set systems to prove a result for certain families of t-intersecting permutations. Specifically, we give the size and structure of a fixed t-intersecting family of permutations provided that n ≥2t + 1 and show that this lower bound on n is optimal.
Open Access
An Erdős-Ko-Rado theorem for the derangement graph of \(PGL_3(q)\) acting on the projective plane
(SIAM J. Discrete Math. 28, 2014) Meagher, Karen; Spiga, Pablo
In this paper we prove an Erdős-Ko-Rado-type theorem for intersecting sets of permutations. We show that an intersecting set of maximal size in the projective general linear group \(PGL_3(q)\), in its natural action on the points of the projective line, is either a coset of the stabilizer of a point or a coset of the stabilizer of a line. This gives the first evidence to the veracity of Conjecture~\(2\) from K.~Meagher, P.~Spiga, An Erdős-Ko-Rado theorem for the derangement graph of \(\mathrm{PGL}(2,q)\) acting on the projective line, \( \textit{J. Comb. Theory Series A} \textbf{118} \) (2011), 532--544.
Open Access
An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective plane
(SIAM Journal on Discrete Mathematics, 2014) Meagher, Karen; Spiga, Pablo
Let G = PGL(2, q) be the projective general linear group acting on the projec- tive line P_q. A subset S of G is intersecting if for any pair of permutations \pi and \sigma in S, there is a projective point p in P_q such that \pi(p)= \sigma(p). We prove that if S is intersecting, then |S| <= q(q-1). Also, we prove that the only sets S that meet this bound are the cosets of the stabilizer of a point of P_q. Keywords: derangement graph, independent sets, Erdos-Ko-Rado
Open Access
The Erdős-Ko-Rado Theorem for Transitive Permutation Groups
(Faculty of Graduate Studies and Research, University of Regina, 2022-03) Razafimahatratra, Andriaherimanana Sarobidy; Meagher, Karen; Fallat, Shaun; Herman, Allen; Yang, Boting; Mojallal, Seyed Ahmad; Bamberg, John
Given a transitive permutation group \(G \le Sym(\Omega)\), a subset \(F\) of \(G\) is \(\textit {intersecting}\) if any two elements of \(F\) agree on some elements of \(\Omega\). We are interested in the problem of finding the structure of the largest intersecting families of \(G\). This problem is the analogue of the \(\textit {Erdős-Ko-Rado (EKR) Theorem}\) for transitive permutation groups. We say that a transitive group \(G \le Sym(\Omega )\) has the \(\textit{EKR property}\) if any intersecting set of \(G\) has size at most the order of a stabilizer of a point of \(G\). Moreover, \(G\) has the \(\textit {strict-EKR property}\) if the largest intersecting sets in \(G\) are cosets of a stabilizer of a point of \(G\). In this thesis, we use various algebraic techniques to prove EKR-type results for finite transitive groups. In particular, we prove that the action of the symmetric group on the 2-tuples with distinct entries and 2-subsets of \([n]\) have the EKR property, and construct families of transitive groups that are as far away as possible from having the EKR property. Then, we show that any transitive subgroup of \(GL_2(q)\) acting on the non-zero vectors of \(\mathbb F^2_q\) has the EKR property. We also prove that for any odd primes \(p\), the size of the largest intersecting set in a transitive group of degree \(2p\) is at most twice the order of a point stabilizer. In addition, we show that if \(G\) is transitive of degree a product of two odd primes, then \(G\) has the EKR property whenever the socle of \(G\) admits an imprimitive subgroup.
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
Fusions of association schemes
(Faculty of Graduate Studies and Research, University of Regina, 2023-01) Joshi, Neha; Allen, Herman; Meagher, Karen; Fallat, Shaun; Floricel, Remus; Fan, Lisa; Sankey, Alyssa
Since their introduction as symmetric coherent configurations by Bose and Mesner in 1959, association schemes have gained significant importance in algebraic combinatorics. An important breakthrough was achieved by Delsarte’s PhD thesis where he proved that many problems from coding theory, combinatorial design theory and statistics can be treated using the concept of association schemes [12]. Since its initial introduction, many algebraists and graph theorists have been studying the existence, construction and generalizations of various association schemes [1, 3, 7, 8, 17, 19, 28, 29, 30]. Because of their impressive construction, association schemes are useful to these subjects and there is always a search for new association schemes. One easy way to construct a new association scheme is by taking either direct or wreath products of two existing association schemes. One such example that we studied was given by Sankey in [32]. Another way to construct a new association scheme is by fusing specific relations of an existing association scheme. The resulting association scheme is known as a fusion (previously referred to as “subscheme” by mathematicians) [4]. The focus of this thesis is to examine a few important association schemes and classify them based on their fusions. It can be observed from literature that the nonexistence of nontrivial fusions is a rare phenomenon and this is the motivation behind this thesis. An association scheme, A, is said to be fusion-primitive if there does not exist any nontrivial fusions of A. In 1992, Muzychuk proved that there does not exist any nontrivial fusions of the Johnson scheme, J (n, k) for all n > 3k + 4 with k ≥ 4 [29]. In 1994, this result was further refined for all n > 3k + 1 by Uchida in [36]. In this thesis, we prove that the Johnson scheme does not have any nontrivial fusions for all n, n > 2k + 1 with k ≤ 20. In addition, we classify almost all of the multiplicity-free subgroups of the symmetric group based on their nontrivial fusions. The Hamming scheme, H(n, q) is an important example in coding theory [10]. The fusionprimitivity of the Hamming scheme has been discussed before (see [28]). In this thesis, we study the generalized Hamming scheme, H(n,A) and prove that it is fusion-imprimitive (that is, it always has a nontrivial fusion). We also classify all fusions of the generalized Hamming scheme, H(2,A) where A is the association scheme corresponding to a strongly-regular graph.
Open Access
A Graph-Theoretic View of Teaching
(Faculty of Graduate Studies and Research, University of Regina, 2012-07) Fan, Gaojian; Zilles, Sandra; Yang, Boting; Yao, Yiyu; Meagher, Karen
In computational learning theory, concepts are subsets of a set of instances and a concept class is a set of concepts. In many computational learning models, learning algorithms have the goal to identify the target concept in a concept class from a small number of examples, i.e., labelled instances. We study graph-theoretic representations of concept classes and their connections to a particular notion of learning complexity, namely teaching complexity. Teaching complexity is a complexity measure for the number of training examples needed in teaching models in which a helpful teacher provides examples to the learner. One type of graph that we study in this thesis is the one-inclusion graph; In this graph the vertices are concepts and there is an edge between two concepts if they disagree on exactly one instance. One-inclusion graphs have proven useful in analyzing some computational learning properties, e.g., sample compression sizes and expected mistake bounds of prediction algorithms. This thesis establishes strong connections between one-inclusion graphs and teaching complexity. We show that the teaching dimension of a concept, i.e., the minimum number of examples required for teaching that concept, is lower bounded by the degree of the corresponding vertex in the one-inclusion graph. Furthermore, we prove that for concepts in shortest-path-closed classes, the lower bounds are always attained. We then prove that the average case teaching complexity of any shortest-path-closed class is linearly upper-bounded by the Vapnik-Chervonenkis (VC) dimension of the class. As the VC dimension reflects the complexity of learning from randomly chosen examples, our theorem gives the evidence that, for the shortest-path-closed concept classes, the average difficulty of learning from a helpful teacher is not higher than that of learning from random examples. We also provide the first characteristic property of shortest-path-closure in terms of minimum teaching sets and the one-inclusion graph. As the one-inclusion graphs only provide partial distinguishing information between concepts, we introduce a new type of graph called minimal Hamming graph which provides the complete distinguishing information between concepts. In contrast to the one-inclusion graph, the vertex degrees in the minimal Hamming graph provide non-trivial upper bounds on the teaching dimension of concepts. Furthermore, we define locally orthogonal concept classes in which the teaching dimension of the concepts always meets the upper bound. We also show that locally orthogonal concept classes generalize the shortest-path-closed classes. We prove that the minimal Hamming graphs of such classes are triangle-free and K2;3-free. Some interesting sufficient conditions for local orthogonality are also studied. We show that the graph-theoretic results on teachability are useful for studying sample compression schemes. A universal sample compression scheme|the peeling sample compression scheme is presented. This compression scheme generalizes some state-of-the-art compression schemes. In addition, we show that the size of this compression scheme is related to teaching complexity if certain graph-theoretic criteria are fulfilled.
Open Access
Intersecting generalized permutations
(2014-01-21) Borg, Peter; Meagher, Karen
Open Access
Maximum Intersecting Families of Permutations
(Faculty of Graduate Studies and Research, University of Regina, 2013-07) Ahmadi, Bahman; Meagher, Karen; Fallat, Shaun; Herman, Allen; Zilles, Sandra; Dukes, Peter
In extremal set theory, the Erd}os-Ko-Rado (EKR) theorem gives an upper bound on the size of intersecting k-subsets of the set {1; : : : ;n}. Furthemore, it classi es the maximum-sized families of intersecting k-subsets. It has been shown that similar theorems can be proved for other mathematical objects with a suitable notion of \intersection". Let G B Sym(n) be a permutation group with its permutation action on the set {1; : : : ;n}. The intersection for the elements of G is de ned as follows: two permutations ; > G are intersecting if (i) = (i) for some i > {1; : : : ;n}. A subset S of G is, then, intersecting if any pair of its elements is intersecting. We say G has the EKR property if the size of any intersecting subset of G is bounded above by the size of a point stabilizer in G. If, in addition, the only maximum-sized intersecting subsets are the cosets of the point-stabilizers in G, then G is said to have the strict EKR property. It was rst shown by Cameron and Ku [10] that the group G = Sym(n) has the strict EKR property. Then Godsil and Meagher presented an entirely di erent proof of this fact using some algebraic properties of the symmetric group. A similar method was employed to prove that the projective general linear group PGL(2; q), with its natural action on the projective line Pq, has the strict EKR property. The main objective in this thesis is to formally introduce this method, which we call the module method, and show that this provides a standard way to prove Erd}os-Ko-Rado theorems for other permutation groups. We then, along with proving Erd}os-Ko-Rado theorems for various groups, use this method to prove some permutation groups have the strict EKR property. We will also show that this method can be useful in characterizing the maximum independent sets of some Cayley graphs. To explain the module method, we need some facts from representation theory of groups, in particular, the symmetric group. We will provide the reader with a su cient level of background from representation theory as well as graph theory and linear algebraic facts about graphs.
Open Access
MIKL´ OS-MANICKAM-SINGHI CONJECTURES ON PARTIAL GEOMETRIES
(2016-06) Meagher, Karen; Ihringer, Ferdinand
In this paper we give a proof of the Mikl´os-Manickam-Singhi (MMS) conjecture for some partial geometries. Specifically, we give a condition on partial geometries which implies that the MMS conjecture holds. Further, several specific partial geometries that are counterexamples to the conjecture are described.
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
Musings on matchings, matrices, and multiplicities
(Faculty of Graduate Studies and Research, University of Regina, 2024-07) Parenteau, Johnna Michele; Fallat, Shaun; Herman, Allen; Meagher, Karen
The Parter-Wiener Theorem is a celebrated contribution to the inverse eigenvalue problem for trees due to its determination of vertices whose removal affects multiplicities of eigenvalues in a non-intuitive manner. For a more general graph, G, that contains cycles, the construction of the weighted matching polynomial and its many properties are derived. These properties are shown to determine a relationship between the multiplicities of the roots of the weighted matching polynomial and the graph operation of vertex deletion in G, which is the operation at the core of the Parter-Wiener Theorem. Solutions for locating vertices whose removal increases the multiplicity of a root are presented, which gives rise to a new classification of graphs, called SRSI graphs. These graphs, along with graphs that have Hamilton paths, are determined to have a trivial variation of the Parter-Wiener Theorem. In an effort to determine the location of Parter vertices, vertices are categorized into classes based on their effects of root multiplicities, and, in the case of zero roots, the location of Parter vertices are explicitly noted. Moreover, computational results regarding the process of categorizing vertices into these classes are outlined, and the Vandermonde eigenvector test is established with the assistance of companion matrices. A myriad of results throughout the thesis are then used to determine a partially-generalized Parter-Wiener Theorem for this weighted matching polynomial.