Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userErdH{o}s-Ko-Rado for Perfect Matchings
112
0
0.0
(
0
)
Authors
Nathan Lindzey
Ask ChatGPT about the research
No Arabic abstract
A perfect matching of a complete graph $K_{2n}$ is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcal{F}| leq (2(n-1) - 1)!!$ and if equality holds, then $mathcal{F} = mathcal{F}_{ij}$ where $ mathcal{F}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. We give a short algebraic proof of this result, resolving a question of Godsil and Meagher. Along the way, we show that if a family $mathcal{F}$ is non-Hamiltonian, that is, $m cup m ot cong C_{2n}$ for any $m,m in mathcal{F}$, then $|mathcal{F}| leq (2(n-1) - 1)!!$ and this bound is met with equality if and only if $mathcal{F} = mathcal{F}_{ij}$. Our results make ample use of a somewhat understudied symmetric commutative association scheme arising from the Gelfand pair $(S_{2n},S_2 wr S_n)$. We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.
rate research
Read More
Let $m$, $n$, and $k$ be integers satisfying $0 < k leq n < 2k leq m$. A family of sets $mathcal{F}$ is called an $(m,n,k)$-intersecting family if $binom{[n]}{k} subseteq mathcal{F} subseteq binom{[m]}{k}$ and any pair of members of $mathcal{F}$ have nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of ErdH{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
Ever since the famous ErdH{o}s-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector spaces and permutations are of particular concerns. Recently, the authors proposed a new quantitative intersection problem for families of subsets: For $mathcal{F}subseteq {[n]choose k}$, define its emph{total intersection number} as $mathcal{I}(mathcal{F})=sum_{F_1,F_2in mathcal{F}}|F_1cap F_2|$. Then, what is the structure of $mathcal{F}$ when it has the maximal total intersection number among all families in ${[n]choose k}$ with the same family size? In cite{KG2020}, the authors studied this problem and characterized extremal structures of families maximizing the total intersection number of given sizes. In this paper, we consider the analogues of this problem for families of vector spaces and permutations. For certain ranges of family size, we provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for some certain values of $|mathcal{F}|$ and characterize the relation between having maximal total intersection number and being intersecting. Besides, we also show several upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes.
In 1935, ErdH{o}s and Szekeres proved that $(m-1)(k-1)+1$ is the minimum number of points in the plane which definitely contain an increasing subset of $m$ points or a decreasing subset of $k$ points (as ordered by their $x$-coordinates). We consider their result from an on-line game perspective: Let points be determined one by one by player A first determining the $x$-coordinate and then player B determining the $y$-coordinate. What is the minimum number of points such that player A can force an increasing subset of $m$ points or a decreasing subset of $k$ points? We introduce this as the ErdH{o}s-Szekeres on-line number and denote it by $text{ESO}(m,k)$. We observe that $text{ESO}(m,k) < (m-1)(k-1)+1$ for $m,k ge 3$, provide a general lower bound for $text{ESO}(m,k)$, and determine $text{ESO}(m,3)$ up to an additive constant.
We provide a cyclic permutation analogue of the ErdH os-Szekeres theorem. In particular, we show that every cyclic permutation of length $(k-1)(ell-1)+2$ has either an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $ell+1$, and show that the result is tight. We also characterize all maximum-length cyclic permutations that do not have an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $ell+1$.
We extend the famous ErdH{o}s-Szekeres theorem to $k$-flats in ${mathbb{R}^d}$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
