BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Karen Meagher

Karen Meagher appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.GRmath.RTmath.ACmath.SP

Catalog footprint

What is connected

29works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

29 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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]$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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\}$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access