2024 CMS Summer Meeting

Saskatchewan, May 30 - June 3, 2024

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Erdos-Ko-Rado Combinatorics
Org: Karen Meagher and Venkata Raghu Tej Pantangi (University of Regina)
[PDF]

SERGEY GORYAINOV, Hebei Normal University Erd\H{o}s-Ko-Rado combinatorics of strongly regular graphs [PDF]

In their book on Erd\H{o}s-Ko-Rado combinatorics, Chris Godsil and Karen Meagher proposed several open problems on strongly regular graphs: Paley graphs of square order, block graphs of orthogonal arrays and block graphs of 2-designs. In my talk I will discuss some recent developments on these open problems.

GLENN HURLBERT, Virginia Commonwealth University Recent results on the Holroyd-Talbot Conjecture [PDF]

In 2005 Holroyd and Talbot generalized the Erd\H{o}s-Ko-Rado realm to graphs by restricting the family of all $r$-subsets of $n$ elements under consideration to the family $\mathcal{I}^r(G)$ of independent sets of size $r$ in a graph $G$ on $n$ vertices. Say that a subfamily of $\mathcal{I}^r(G)$ is a {\it star} if the intersection of its sets (its {\it center}) is nonempty. Let $\mathcal{F}$ be an intersecting subfamily of $\mathcal{I}^r(G)$ and denote the minimum size of a maximal independent set in $G$ by $\mu(G)$. They conjectured that if $r \le \mu(G)/2$ then the size of $\mathcal{F}$ is at most the size of some star.

After a brief history of earlier results by Deza-Frankl, Bollob\'as-Leader, and others, I will present more recent theorems and open problems with various collaborators including Feghali, Frankl, Kamat, and Meagher. Among the results are injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems, certification of the Holroyd-Talbot conjecture for smaller $r$ on sparse graphs, and partial results and conjectures on trees regarding where the center of a largest star can be.

LORD KAVI, University of Ottawa Optimal Polynomials for the $k$-independence Number of Graphs [PDF]

A $k$-independent set in a graph is a set of vertices such that any two vertices in the set are at distance at least $k+1$ in the graph. The $k$-independence number of a graph, denoted $\alpha_k$, is the size of a largest $k$-independent set in the graph. Abiad et al gave a generalization of the Hoffman ratio bound on $\alpha_k$, which involves taking polynomials of degree at most $k$. A good bound therefore depends on making the right choice of a polynomial. In this talk, we highlight the known optimal polynomials for $k=1,2,3$ and their corresponding bounds on $\alpha_k$, and give a possible generalization of these polynomials.

ANDREY KUPAVSKII, Moscow Institute of Physics and Technology Forbidden intersections via spread approximations [PDF]

I will speak about the recent progress on the Erdos-Ko-Rado type results for different structures, such as sets, partitions and permutations, that we have managed to obtain using the method of spread approximations. In particular, I will cover the progress on the Frankl-Deza problem about t-intersecting permutations and the resolution of the Meagher-Moura question on partially t-intersecting families of partitions.

NATHAN LINDZEY, Technion Global Hypercontractivity and Forbidden Intersection Theorems [PDF]

Hypercontractive inequalities play a fundamental role in discrete Fourier analysis over the hypercube and have many applications throughout Discrete Mathematics. Such inequalities continue to hold in other combinatorial domains, but for a restricted class of functions that satisfy a pseudorandomness condition called globalness. We give an overview of global hypercontractivity and its application to Erdős–Ko–Rado and Erdős–Sós-type forbidden intersection theorems for various non-Abelian matrix groups. This is joint work with Esty Kelman and Ohad Sheinfeld.

KAREN MEAGHER, University of Regina A brief Introduction to the Erdős-Ko-Rado Theorem [PDF]

My talk will be a short introduction to the Erdős-Ko-Rado (EKR) Theorem. I will start by giving the standard version of the EKR theorem, and state some of the versions for other objects. Next I will give an overview of some of the common proof methods (such as the kernel method, compression, derangement graphs and the ratio bound). Finally, I will end with some result related to the EKR theorem, such as the Hilton-Milner theorem, and new directions in this area.

VENKATA RAGHU TEJ PANTANGI, University of Regina Strength of some EKR-type results. [PDF]

The classical Erdos-Ko-Rado (EKR) theorem and its variants can be translated into characterizing maximum co-cliques of graphs in Association schemes. For instance, the classical Erd\H{o}s-Ko-Rado characterizes maximum co-cliques in the Kneser graph. Given a graph $G$, by $G_{p}$, we denote the random subgraph of $G$ in which edges appear independently, each with a probability $p$. In this talk, we consider the following question: for which probabilities is the independence number of $G_{p}$ equal to that of $G$? Bollabas-Narayanan-Raigorodskii investigated the independence numbers of random subgraphs of the Kneser graph. In this talk, we will investigate the independence numbers of random subgraphs of (i) the derangement graph on permutations; and (ii) the perfect matching graphs. The derangement graph is associated with the EKR type result on permutations and the perfect matching graph is associated with EKR type result on perfect matchings. This is joint work with the members of the PIMS Collaborative Research Group on Movement and Symmetry in graphs.

SAROBIDY RAZAFIMAHATRATRA, University of Primorska The Erdős-Ko-Rado Theorem for semidirect products of transitive groups [PDF]

A set of permutations $\mathcal{F}$ of a finite transitive group $G\leq \operatorname{Sym}(\Omega)$ is \emph{intersecting} if any two permutations in $\mathcal{F}$ agree on some elements of $\Omega$. An Erdős-Ko-Rado (EKR) type theorem for the transitive group $G$ in this context gives the size and the structure of the largest intersecting sets.

In 2015, Ahmadi and Meagher asked whether it is possible to give an EKR type theorem for the semidirect product $G\rtimes \mathbb{Z}_2 \leq \operatorname{Sym}(\Omega)$, provided that we have a ``nice enough'' EKR theorem for the transitive group $G\leq \operatorname{Sym}(\Omega)$. There is no general answer to this question and the structure of the largest intersecting sets vastly depends on the action of $G$.

In this talk, I will focus on an example of semidirect product with cyclic groups for which the largest intersecting sets are much more complex. In particular, I will talk about the largest intersecting sets for the actions of the general linear group $\operatorname{GL}_2(q)$ and the general semilinear group $\operatorname{\Gamma L}_2(q) = \operatorname{GL}_2(q) \rtimes \operatorname{Aut}(\mathbb{F}_q)$ on non-zero vectors of $\mathbb{F}_q^2$. Note that if $p$ is a prime, then $\operatorname{\Gamma L}_2(p^2) = \operatorname{GL}_2(p^2) \rtimes \mathbb{Z}_2$. In contrast to $\operatorname{GL}_2(q)$ which only has two classes of largest intersecting sets, the group $\operatorname{\Gamma L}_2(q)$ has multiple classes of intersecting sets, and they need not be subgroups.

MAHSA SHIRAZI, University of Manitoba A review on the Erdős-Ko-Rado theorem for uniform set partitions and perfect matchings [PDF]

A "perfect matching" in a graph, is a set of edges by which every vertex is covered exactly once. A perfect matching is in fact a special case of a "uniform set partition". A uniform set partition is a partition in which all parts have the same size. In this talk, we will review some results on the Erdős-Ko-Rado theorem for perfect matchings and uniform set partitions. Particularly, we focus on $2$-intersecting and set-wise $2$-intersecting perfect matchings and partially $2$-intersecting uniform set partitions.

CODY SOLIE, University of Regina Database of Intersection Density for Permutation Groups [PDF]

The intersection density of a permutation group is the ratio of the size of a largest intersecting set in a permutation group, compared to the size of the stabilizer of a point. Many families of groups have been shown to have intersection density equal to 1. Recent work has tried to find groups with intersection density larger than one. A key tool for this work which has been missing is a centralized, comprehensive database of known intersection density for small groups. We are working to create this database as a public resource, and we will discuss our computational techniques and relevant theory which allow us to gather these results.

BRETT STEVENS, Carleton University Where Karen Meagher first encountered the Erdos-Ko-Rado Theorem [PDF]

Karen Meagher first encountered the Erdos-Ko-Rado theorem when studying covering arrays. The Erdos-Ko-Rado theorem and Sperner's Lemma form the basis for the only known construction of an infinite family of optimal non-orthogonal covering arrays. I will define covering arrays, talk about their applications but concentrate the talk on the beautiful theorem of Renyi and Katona that determines the optimal size of binary covering arrays of strength 2. This encounter was the beginning of Karen's productive relationship with Erdos-Ko-Rado type problems.

top of page