Source author record

Karen Meagher

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR math.RT math.AC math.SP

Catalog footprint

Research overview

29works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

All $2$ -transitive groups have the EKR-module property

We prove that every 2-transitive group has a property called the EKR-module property. This property gives a characterization of the maximum intersecting sets of permutations in the group. Specifically, the characteristic vector of any maximum intersecting set in a 2-transitive group is the linear combination of the characteristic vectors of the stabilizers of a points and their cosets. We also consider when the derangement graph of a 2-transitive group is connected and when a maximum intersecting set is a subgroup or a coset of a subgroup.

preprint2022arXiv

An upper bound for the $k$ -power domination number in $r$ -uniform hypergraphs

Generalizing work on graphs, Chang and Roussel introduced $k$ -power domination in hypergraphs and conjectured the upper bound for the $k$ -power domination number for $r$ -uniform hypergraphs on $n$ vertices was $\frac{n}{r+k}$ . This upper bound was shown to be true for simple graphs ( $r=2$ ) and it was further conjectured that only a family of hypergraphs, known as the squid hypergraphs, attained this upper bound. In this paper, the conjecture is proven to hold for hypergraphs with $r=3$ or $4$ ; but is shown to be false, by a counterexample, for $r\geq 7$ . Furthermore, we show that the squid hypergraphs are not the only hypergraphs that attain the original upper bound. Finally, a new upper bound is proven for $r\geq 3$ .

preprint2022arXiv

Fusions of the generalized Hamming scheme on a strongly-regular graph

In this paper we show that for any fusion $\mathcal{B}$ of an association scheme $\mathcal{A}$ , the generalized Hamming scheme $H(n,\mathcal{B})$ is a nontrivial fusion of $H(n,\mathcal{A})$ . We analyze the case where $\mathcal{A}$ is the association scheme on a strongly-regular graph, and determine the parameters of all strongly-regular graphs for which the generalized Hamming scheme, $H(2,\mathcal{A})$ , has extra fusions, in addition to the one arising from the trivial fusion of $\mathcal{A}$ .

preprint2021arXiv

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

We investigate strongly regular graphs for which Hoffman's ratio bound and Cvetcović's inertia bound are equal. This means that $ve^- = m^-(e^- - k)$ , where $v$ is the number of vertices, $k$ is the regularity, $e^-$ is the smallest eigenvalue, and $m^-$ is the multiplicity of $e^-$ . We show that Delsarte cocliques do not exist for all Taylor's $2$ -graphs and for point graphs of generalized quadrangles of order $(q,q^2-q)$ for infinitely many $q$ . For cases where equality may hold, we show that for nearly all parameter sets, there are at most two Delsarte cocliques.

preprint2020arXiv

On triangles in derangement graphs

Given a permutation group $G$ , the derangement graph $Γ_G$ of $G$ is the Cayley graph with connection set the set of all derangements of $G$ . We prove that, when $G$ is transitive of degree at least $3$ , $Γ_G$ contains a triangle. The motivation for this work is the question of how large can be the ratio of the independence number of $Γ_G$ to the size of the stabilizer of a point in $G$ . We give examples of transitive groups where this ratio is maximum.

preprint2020arXiv

The Erdős-Ko-Rado theorem for $2$ -intersecting families of perfect matchings

A perfect matching in the complete graph on $2k$ vertices is a set of edges such that no two edges have a vertex in common and every vertex is covered exactly once. Two perfect matchings are said to be $t$ -intersecting if they have at least $t$ edges in common. The main result in this paper is an extension of the famous Erdős-Ko-Rado (EKR) theorem \cite{EKR} to 2-intersecting families of perfect matchings for all values of $k$ . Specifically, for $k\geq 3$ a set of 2-intersecting perfect matchings in $K_{2k}$ of maximum size has $(2k-5)(2k-7)\cdots (1)$ perfect matchings.

preprint2016arXiv

Brushing Number and Zero-Forcing Number of Graphs and their Line Graphs

In this paper we compare the brushing number of a graph with the zero-forcing number of its line graph. We prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Using a similar construction, we also prove the conjecture that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph; moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight.

preprint2016arXiv

Infection in Hypergraphs

In this paper a new parameter for hypergraphs called hypergraph infection is defined. This concept generalizes zero forcing in graphs to hypergraphs. The exact value of the infection number of complete and complete bipartite hypergraphs is determined. A formula for the infection number for interval hypergraphs and several families of cyclic hypergraphs is given. The value of the infection number for a hypergraph whose edges form a symmetric t-design is given, and bounds are determined for a hypergraph whose edges are a t-design. Finally, the infection number for several hypergraph products and line graphs are considered.

preprint2015arXiv

An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings

In this paper we give a proof that the largest set of perfect matchings, in which any two contain a common edge, is the set of all perfect matchings that contain a fixed edge. This is a version of the famous Erdős-Ko-Rado theorem for perfect matchings. The proof given in this paper is algebraic, we first determine the least eigenvalue of the perfect matching derangement graph and use properties of the perfect matching polytope. We also prove that the perfect matching derangement graph is not a Cayley graph.

preprint2015arXiv

An Erdős-Ko-Rado theorem for finite 2-transitive groups

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 X, we show that an intersecting set of maximal size in G has cardinality |G|/|X|. This generalises and gives a unifying proof of some similar recent results in the literature.

preprint2015arXiv

Compressed Cliques Graphs, Clique Coverings and Positive Zero Forcing

Zero forcing parameters, associated with graphs, have been studied for over a decade, and have gained popularity as the number of related applications grows. In particular, it is well-known that such parameters are related to certain vertex coverings. Continuing along these lines, we investigate positive zero forcing within the context of certain clique coverings. A key object considered here is the compressed cliques graph. We study a number of properties associated with the compressed cliques graph, including: uniqueness, forbidden subgraphs, connections to Johnson graphs, and positive zero forcing.

preprint2015arXiv

Graphs that have a weighted adjacency matrix with spectrum $\{λ_1^{n-2}, λ_1^2\}$

In this paper we completely characterize the graphs which have an edge weighted adjacency matrix belonging to the class of $n \times n$ involutions with spectrum equal to $\{ λ_1^{n-2}, λ_2^{2} \}$ for some $λ_1$ and some $λ_2$ . The connected graphs turn out to be the cographs constructed as the join of at least two unions of pairs of complete graphs, and possibly joined with one other complete graph.

preprint2015arXiv

Intersection theorems for multisets

Let $k$ , $t$ and $m$ be positive integers. A $k$ -multiset of $[m]$ is a collection of $k$ integers from the set $\{1,...,m\}$ in which the integers can appear more than once. We use graph homomorphisms and existing theorems for intersecting and $t$ -intersecting $k$ -set systems to prove new results for intersecting and $t$ -intersecting families of $k$ -multisets. These results include a multiset version of the Hilton-Milner theorem and a theorem giving the size and structure of the largest $t$ -intersecting family of $k$ -multisets of an $m$ -set when $m \leq 2k-t$ .

preprint2014arXiv

Intersecting generalised permutations

For any positive integers $k,r,n$ with $r \leq \min\{k,n\}$ , let $\mathcal{P}_{k,r,n}$ be the family of all sets $\{(x_1,y_1), \dots, (x_r,y_r)\}$ such that $x_1, \dots, x_r$ are distinct elements of $[k] = \{1, \dots, k\}$ and $y_1, \dots, y_r$ are distinct elements of $[n]$ . The families $\mathcal{P}_{n,n,n}$ and $\mathcal{P}_{n,r,n}$ describe permutations of $[n]$ and $r$ -partial permutations of $[n]$ , respectively. If $k \leq n$ , then $\mathcal{P}_{k,k,n}$ describes permutations of $k$ -element subsets of $[n]$ . A family $\mathcal{A}$ of sets is said to be intersecting if every two members of $\mathcal{A}$ intersect. In this note we use Katona's elegant cycle method to show that a number of important Erdős-Ko-Rado-type results by various authors generalise as follows: the size of any intersecting subfamily $\mathcal{A}$ of $\mathcal{P}_{k,r,n}$ is at most ${k-1 \choose r-1}\frac{(n-1)!}{(n-r)!}$ , and the bound is attained if and only if $\mathcal{A} = \{A \in \mathcal{P}_{k,r,n} \colon (a,b) \in A\}$ for some $a \in [k]$ and $b \in [n]$ .

preprint2014arXiv

On the Complexity of the Positive Semidefinite Zero Forcing Number

The positive zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring, and is related to a more conventional version of zero forcing. We establish a relation between the zero forcing and the fast-mixed searching, which implies some NP-completeness results for the zero forcing problem. For chordal graphs much is understood regarding the relationships between positive zero forcing and clique coverings. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive zero forcing number of chordal graphs. We also prove that it is NP-complete to determine if a graph has a positive zero forcing set with an additional property.

preprint2013arXiv

A new proof for the Erdős-Ko-Rado Theorem for the alternating group

A subset $S$ of the alternating group on $n$ points is {\it intersecting} if for any pair of permutations $π,σ$ in $S$ , there is an element $i\in \{1,\dots,n\}$ such that $π(i)=σ(i)$ . We prove that if $S$ is intersecting, then $|S|\leq \frac{(n-1)!}{2}$ . Also, we prove that if $n \geq 5$ , then the only sets $S$ that meet this bound are the cosets of the stabilizer of a point of $\{1,\dots,n\}$ .

preprint2013arXiv

An Erdős-Ko-Rado theorem for subset partitions

A $k\ell$ -subset partition, or $(k,\ell)$ -subpartition, is a $k\ell$ -subset of an $n$ -set that is partitioned into $\ell$ distinct classes, each of size $k$ . Two $(k,\ell)$ -subpartitions are said to $t$ -intersect if they have at least $t$ classes in common. In this paper, we prove an Erdős-Ko-Rado theorem for intersecting families of $(k,\ell)$ -subpartitions. We show that for $n \geq k\ell$ , $\ell \geq 2$ and $k \geq 3$ , the largest $1$ -intersecting family contains at most $\frac{1}{(\ell-1)!}\binom{n-k}{k}\binom{n-2k}{k}\cdots\binom{n-(\ell-1)k}{k}$ $(k,\ell)$ -subpartitions, and that this bound is only attained by the family of $(k,\ell)$ -subpartitions with a common fixed class, known as the \emph{canonical intersecting family of $(k,\ell)$ -subpartitions}. Further, provided that $n$ is sufficiently large relative to $k,\ell$ and $t$ , the largest $t$ -intersecting family is the family of $(k,\ell)$ -subpartitions that contain a common set of $t$ fixed classes.

preprint2013arXiv

An Erdős-Ko-Rado theorem for the derangement graph of PGL(3,q) acting on the projective plane

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.

preprint2013arXiv

On the Relationships between Zero Forcing Numbers and Certain Graph Coverings

The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph. We show that for a block-cycle graph the zero forcing number equals the path cover number. We also give a purely graph theoretical proof that the positive zero forcing number of any outerplanar graphs equals the tree cover number of the graph. These ideas are then extended to the setting of $k$ -trees, where the relationship between the positive zero forcing number and the tree cover number becomes more complex.

preprint2013arXiv

The Erdős-Ko-Rado property for some 2-transitive groups

A subset of a group G of Sym(n) is intersecting if for any pair of permutations $π,σ\in G$ there is an $i$ in {1,2,...,n} such that $π(i) = σ(i)$ . It has been shown, using an algebraic approach, that the largest intersecting sets in each of Sym(n), Alt(n) and PGL(2,q) are exactly the cosets of the point-stabilizers. In this paper, we show how this method can be applied more generally to many 2-transitive groups. We then apply this method to the Mathieu groups and to all 2-transtive groups with degree no more than 20.

preprint2013arXiv

The Erdős-Ko-Rado property for some permutation groups

A subset in a group $G \leq Sym(n)$ is intersecting if for any pair of permutations $π,σ$ in the subset there is an $i \in \{1,2,\dots,n\}$ such that $π(i) = σ(i)$ . If the stabilizer of a point is the largest intersecting set in a group, we say that the group has the Erdős-Ko-Rado (EKR) property. Moreover, the group has the strict EKR property if every intersecting set of maximum size in the group is either the stabilizer of a point or the coset of the stabilizer of a point. In this paper we look at several families of permutation groups and determine if the groups have either the EKR property or the strict EKR property. First, we prove that all cyclic groups have the strict EKR property. Next we show that all dihedral and Frobenius groups have the EKR property and we characterize which ones have the strict EKR property. Further, we show that if all the groups in an external direct sum or an internal direct sum have the EKR (or strict EKR) property, then the product does as well. Finally, we show that the wreath product of two groups with EKR property also has the EKR property.

preprint2013arXiv

The exact bound for the Erdős-Ko-Rado theorem for $t$ -cycle-intersecting permutations

In this paper we adapt techniques used by Ahlswede and Khachatrian in their proof of the Complete Erdős-Ko-Rado Theorem to show that if $n \geq 2t+1$ , then any pairwise $t$ -cycle-intersecting family of permutations has cardinality less than or equal to $(n-t)!$ . Furthermore, the only families attaining this size are the stabilizers of $t$ points, that is, families consisting of all permutations having $t$ 1-cycles in common. This is a strengthening of a previous result of Ku and Renshaw and supports a recent conjecture by Ellis, Friedgut and Pilpel concerning the corresponding bound for $t$ -intersecting families of permutations.

preprint2012arXiv

Resolving sets for Johnson and Kneser graphs

A set of vertices $S$ in a graph $G$ is a {\em resolving set} for $G$ if, for any two vertices $u,v$ , there exists $x\in S$ such that the distances $d(u,x) \neq d(v,x)$ . In this paper, we consider the Johnson graphs $J(n,k)$ and Kneser graphs $K(n,k)$ , and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.

preprint2012arXiv

Sperner partition systems

A \textsl{Sperner $k$ -partition system} on a set $X$ is a set of partitions of $X$ into $k$ classes such that the classes of the partitions form a Sperner set system (so no class from a partition is a subset of a class from another partition). These systems were defined by Meagher, Moura and Stevens in \cite{MMS} who showed that if $|X| = k \ell$ , then the largest Sperner $k$ -partition system has size $\frac{1}{k}\binom{|X|}{\ell}$ . In this paper we find bounds on the size of the largest Sperner $k$ -partition system where $k$ does not divide the size of $X$ , specifically, we give an exact bound when $k=2$ and upper and lower bounds when $|X| = 2k+1$ , $|X|=2k+2$ and $|X| = 3k-1$ .

preprint2011arXiv

An Erdős-Ko-Rado theorem for multisets

Let $k$ and $m$ be positive integers. A collection of $k$ -multisets from $\{1,..., m \}$ is intersecting if every pair of multisets from the collection is intersecting. We prove that for $m \geq k+1$ , the size of the largest such collection is $\binom{m+k-2}{k-1}$ and that when $m > k+1$ , only a collection of all the $k$ -multisets containing a fixed element will attain this bound. The size and structure of the largest intersecting collection of $k$ -multisets for $m \leq k$ is also given.

preprint2011arXiv

Generalized covering designs and clique coverings

Inspired by the "generalized t-designs" defined by Cameron [P. J. Cameron, A generalisation of t-designs, Discrete Math. 309 (2009), 4835--4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs.

preprint2011arXiv

On the metric dimension of Grassmann graphs

The {\em metric dimension} of a graph $Γ$ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph $G_q(n,k)$ (whose vertices are the $k$ -subspaces of $\mathbb{F}_q^n$ , and are adjacent if they intersect in a $(k-1)$ -subspace) for $k\geq 2$ , and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of $\mathbb{F}_q^n$ .

preprint2011arXiv

The minimum rank of universal adjacency matrices

In this paper we introduce a new parameter for a graph called the {\it minimum universal rank}. This parameter is similar to the minimum rank of a graph. For a graph $G$ the minimum universal rank of $G$ is the minimum rank over all matrices of the form $U(α, β, γ, δ) = αA + βI + γJ + δD$ where $A$ is the adjacency matrix of $G$ , $J$ is the all ones matrix and $D$ is the matrix with the degrees of the vertices in the main diagonal, and $α\neq 0, β, γ, δ$ are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of $A$ . The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. Finally we characterize all graphs with minimum universal rank equal to 0 and to 1.

preprint2010arXiv

An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective line

Let G=PGL(2,q) be the projective general linear group acting on the projective line P_q. A subset S of G is intersecting if for any pair of permutations π,σin S, there is a projective point p in P_q such that p^π=p^σ. We prove that if S is intersecting, then the size of S is no more than 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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Karen Meagher

Research overview

Is this your work?

29 publications

All $2$ -transitive groups have the EKR-module property

An upper bound for the $k$ -power domination number in $r$ -uniform hypergraphs

Fusions of the generalized Hamming scheme on a strongly-regular graph

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

On triangles in derangement graphs

The Erdős-Ko-Rado theorem for $2$ -intersecting families of perfect matchings

Brushing Number and Zero-Forcing Number of Graphs and their Line Graphs

Infection in Hypergraphs

An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings

An Erdős-Ko-Rado theorem for finite 2-transitive groups

Compressed Cliques Graphs, Clique Coverings and Positive Zero Forcing

Graphs that have a weighted adjacency matrix with spectrum $\{λ_1^{n-2}, λ_1^2\}$

Intersection theorems for multisets

Intersecting generalised permutations

On the Complexity of the Positive Semidefinite Zero Forcing Number

A new proof for the Erdős-Ko-Rado Theorem for the alternating group

An Erdős-Ko-Rado theorem for subset partitions

An Erdős-Ko-Rado theorem for the derangement graph of PGL(3,q) acting on the projective plane

On the Relationships between Zero Forcing Numbers and Certain Graph Coverings

The Erdős-Ko-Rado property for some 2-transitive groups

The Erdős-Ko-Rado property for some permutation groups

The exact bound for the Erdős-Ko-Rado theorem for $t$ -cycle-intersecting permutations

Resolving sets for Johnson and Kneser graphs

Sperner partition systems

An Erdős-Ko-Rado theorem for multisets

Generalized covering designs and clique coverings

On the metric dimension of Grassmann graphs

The minimum rank of universal adjacency matrices

An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective line

See the researcher in context

Building this map preview

Karen Meagher

Research overview

Is this your work?

29 publications

All 222-transitive groups have the EKR-module property

An upper bound for the kkk-power domination number in rrr-uniform hypergraphs

Fusions of the generalized Hamming scheme on a strongly-regular graph

Ovoids of Generalized Quadrangles of Order (q,q2−q)(q, q^2-q)(q,q2−q) and Delsarte Cocliques in Related Strongly Regular Graphs

On triangles in derangement graphs

The Erdős-Ko-Rado theorem for 222-intersecting families of perfect matchings

Brushing Number and Zero-Forcing Number of Graphs and their Line Graphs

Infection in Hypergraphs

An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings

An Erdős-Ko-Rado theorem for finite 2-transitive groups

Compressed Cliques Graphs, Clique Coverings and Positive Zero Forcing

Graphs that have a weighted adjacency matrix with spectrum {λ1n−2,λ12}\{λ_1^{n-2}, λ_1^2\}{λ1n−2​,λ12​}

Intersection theorems for multisets

Intersecting generalised permutations

On the Complexity of the Positive Semidefinite Zero Forcing Number

A new proof for the Erdős-Ko-Rado Theorem for the alternating group

An Erdős-Ko-Rado theorem for subset partitions

An Erdős-Ko-Rado theorem for the derangement graph of PGL(3,q) acting on the projective plane

On the Relationships between Zero Forcing Numbers and Certain Graph Coverings

The Erdős-Ko-Rado property for some 2-transitive groups

The Erdős-Ko-Rado property for some permutation groups

The exact bound for the Erdős-Ko-Rado theorem for ttt-cycle-intersecting permutations

Resolving sets for Johnson and Kneser graphs

Sperner partition systems

An Erdős-Ko-Rado theorem for multisets

Generalized covering designs and clique coverings

On the metric dimension of Grassmann graphs

The minimum rank of universal adjacency matrices

An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective line

See the researcher in context

Building this map preview

All $2$ -transitive groups have the EKR-module property

An upper bound for the $k$ -power domination number in $r$ -uniform hypergraphs

Ovoids of Generalized Quadrangles of Order $(q, q^2-q)$ and Delsarte Cocliques in Related Strongly Regular Graphs

The Erdős-Ko-Rado theorem for $2$ -intersecting families of perfect matchings

Graphs that have a weighted adjacency matrix with spectrum $\{λ_1^{n-2}, λ_1^2\}$

The exact bound for the Erdős-Ko-Rado theorem for $t$ -cycle-intersecting permutations