The Ratio Bound for Erdős-Ko-Rado Type Theorems

Abstract: In this talk Karen Meagher will introduce the Ratio Bound, also called Hoffman's Bound or Delsarte's Bound. This is an algebraic bound the size of the maximum coclique/independent set in a graph. This bound has been used to prove many variations of the Erdős-Ko-Rado theorem. She will outline some examples of such problems and will show how it can be used effectively for such problems.

Then Sarobidy Razafimahatratra will use the Hoffman Bound to prove the Erdős-Ko-Rado theorem for transitive groups. A set of permutations $\mathcal{F}$ of a finite transitive group $G\leq \operatorname{Sym}(\Omega)$ is intersecting if any two permutations in $\mathcal{F}$ agree on an element of $\Omega$. The transitive group $G$ is said to have the Erdős-Ko-Rado (EKR) property if any intersecting set of $G$ has size at most $\frac{|G|}{|\Omega|}$. The alternating group $\operatorname{Alt}(4)$ acting on the six $2$-subsets of $\{1,2,3,4\}$ is an example of groups without the EKR property. This means that transitive groups do not always have the EKR property. Given a transitive group $G\leq\operatorname{Sym}(\Omega)$, we are interested in finding the size and structure of the largest intersecting sets in $G$. In this talk, we will use the Hoffman bound to prove the EKR property for some families of transitive groups.

Finally, Mahsa Nasrollahi Shirazi will prove an extension of the Erdős-Ko-Rado theorem to set-wise intersecting perfect matchings. Two perfect matchings $P$ and $Q$ of a graph on $2k$ vertices are said to be set-wise $t$-intersecting if there exist edges $P_{1}, \ldots, P_{t}$ in $P$ and $Q_{1}, \ldots, Q_{t}$ in $Q$ such that the union of edges $P_{1}, \ldots, P_{t}$ has the same set of vertices as the union of $Q_{1}, \ldots, Q_{t}$. We define a graph for which finding a maximum coclique is equivalent to finding a largest family of set-wise $t$-intersecting perfect matchings for $t=2,3$. In this approach we use the ratio bound to find bounds on the size of a maximum coclique in this graph.

combinatorics

Audience: researchers in the topic

( slides | video )

---

Carleton Combinatorics Meeting 2021

Series comments: See the external webpage for more details: people.math.carleton.ca/~dthomson/CCM2021

To contact, please use CCM2021@math.carleton.ca and prefix your subject with "[CCM2021-request]"

---