ErdosKoRado Combinatorics
Org:
Karen Meagher and
Venkata Raghu Tej Pantangi (University of Regina)
[
PDF]
 SERGEY GORYAINOV, Hebei Normal University
Erd\H{o}sKoRado combinatorics of strongly regular graphs [PDF]

In their book on Erd\H{o}sKoRado 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 2designs. In my talk I will discuss some recent developments on these open problems.
 GLENN HURLBERT, Virginia Commonwealth University
Recent results on the HolroydTalbot Conjecture [PDF]

In 2005 Holroyd and Talbot generalized the Erd\H{o}sKoRado 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 DezaFrankl, Bollob\'asLeader, 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ősKoRado and HiltonMilner theorems, certification of the HolroydTalbot 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 ErdosKoRado 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 FranklDeza problem about tintersecting permutations and the resolution of the MeagherMoura question on partially tintersecting 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óstype forbidden intersection theorems for various nonAbelian matrix groups. This is joint work with Esty Kelman and Ohad Sheinfeld.
 KAREN MEAGHER, University of Regina
A brief Introduction to the ErdősKoRado Theorem [PDF]

My talk will be a short introduction to the ErdősKoRado (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 HiltonMilner theorem, and new directions in this area.
 VENKATA RAGHU TEJ PANTANGI, University of Regina
Strength of some EKRtype results. [PDF]

The classical ErdosKoRado (EKR) theorem and its variants can be translated into characterizing maximum cocliques of graphs in Association schemes. For instance, the classical Erd\H{o}sKoRado characterizes maximum cocliques 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$? BollabasNarayananRaigorodskii 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ősKoRado 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ősKoRado (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 nonzero 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ősKoRado 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ősKoRado theorem for perfect matchings and uniform set partitions. Particularly, we focus on $2$intersecting and setwise $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 ErdosKoRado Theorem [PDF]

Karen Meagher first encountered the ErdosKoRado theorem when studying covering arrays. The ErdosKoRado theorem and Sperner's Lemma form the basis for the only known construction of an infinite family of optimal nonorthogonal 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 ErdosKoRado type problems.
© Canadian Mathematical Society