Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntersecting Families of Perfect Matchings
99
0
0.0
(
0
)
Authors
Nathan Lindzey
Ask ChatGPT about the research
No Arabic abstract
A family of perfect matchings of $K_{2n}$ is $t$-$intersecting$ if any two members share $t$ or more edges. We prove for any $t in mathbb{N}$ that every $t$-intersecting family of perfect matchings has size no greater than $(2(n-t) - 1)!!$ for sufficiently large $n$, and that equality holds if and only if the family is composed of all perfect matchings that contain a fixed set of $t$ disjoint edges. This is an asymptotic version of a conjecture of Godsil and Meagher that can be seen as the non-bipartite analogue of the Deza-Frankl conjecture proven by Ellis, Friedgut, and Pilpel.
rate research
Read More
A family of perfect matchings of $K_{2n}$ is $intersecting$ if any two of its members have an edge in common. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcal{F}| leq (2n-3)!!$ 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$. In this note, we show that the extremal families are stable, namely, that for any $epsilon in (0,1/sqrt{e})$ and $n > n(epsilon)$, any intersecting family of perfect matchings of size greater than $(1 - 1/sqrt{e} + epsilon)(2n-3)!!$ is contained in $mathcal{F}_{ij}$ for some edge $ij$. The proof uses the Gelfand pair $(S_{2n},S_2 wr S_n)$ along with an isoperimetric method of Ellis.
A family of sets is said to be emph{symmetric} if its automorphism group is transitive, and emph{intersecting} if any two sets in the family have nonempty intersection. Our purpose here is to study the following question: for $n, kin mathbb{N}$ with $k le n/2$, how large can a symmetric intersecting family of $k$-element subsets of ${1,2,ldots,n}$ be? As a first step towards a complete answer, we prove that such a family has size at most [expleft(-frac{c(n-2k)log n}{k( log n - log k)} right) binom{n}{k},] where $c > 0$ is a universal constant. We also describe various combinatorial and algebraic approaches to constructing such families.
We shall be interested in the following Erdos-Ko-Rado-type question. Fix some subset B of [n]. How large a family A of subsets of [n] can we find such that the intersection of any two sets in A contains a cyclic translate (modulo n) of B? Chung, Graham, Frankl and Shearer have proved that, in the case where B is a block of length t, we can do no better than to take A to consist of all supersets of B. We give an alternative proof of this result, which is in a certain sense more direct.
Let $mathcal{F}$ and $mathcal{G}$ be two $t$-uniform families of subsets over $[k] = {1,2,...,k}$, where $|mathcal{F}| = |mathcal{G}|$, and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $mathcal{F}$ and $mathcal{G}$, and there is an edge between $Ain mathcal{F}$ and $B in mathcal{G}$ if and only if $A cap B eq emptyset$. The pair $(mathcal{F},mathcal{G})$ is $q$-almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $q$-almost cross intersecting pairs that have a circulant intersection matrix $C_{p,q}$, determined by a column vector with $p > 0$ ones followed by $q > 0$ zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme. We give constructions of pairs $(mathcal{F},mathcal{G})$ whose intersection matrix is $C_{p,q}$, for a wide range of values of the parameters $p$ and $q$, and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) $1 leq p leq 2t-1$ and $1 leq q leq k-2t+1$. (2) $2t leq p leq t^2$ and any $q> 0$, where $k geq p+q$. (3) $p$ that is exponential in $t$, for large enough $k$. Using the first result we show that if $k geq 4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $ktimes k$ in the $0,1$-matrix $A_{k,t}$, whose rows and columns are labeled by all subsets of size $t$ of $[k]$, and there is a one in the entry on row $x$ and column $y$ if and only if subsets $x,y$ intersect.
A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independently showed that for $ngeq 2k + csqrt{kln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $ngeq 2k+ 100ln k$. Our proof uses, among others, Sapozhenkos graph container lemma and the Das-Tran removal lemma.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
