Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInverse problems of the ErdH{o}s-Ko-Rado type theorems for families of vector spaces and permutations
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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$.
Generalized Turan problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.
For positive integers $n>dgeq k$, let $phi(n,d,k)$ denote the least integer $phi$ such that every $n$-vertex graph with at least $phi$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, ErdH{o}s, Faudree, Schelp and Simonovits proposed the study of the function $phi(n,d,k)$, and conjectured that for any positive integers $n>dgeq k$, it holds that $phi(n,d,k)leq lfloorfrac{k-1}{2}rfloorlfloorfrac{n}{d+1}rfloor+epsilon$, where $epsilon=1$ if $k$ is odd and $epsilon=2$ otherwise. In this paper we determine the value of the function $phi(n,d,k)$ exactly. This confirms the above conjecture of ErdH{o}s et al. for all positive integers $k eq 4$ and in a corrected form for the case $k=4$. Our proof utilizes, among others, a lemma of ErdH{o}s et al., a theorem of Jackson, and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin, where the latter two results concern maximum cycles in bipartite graphs. Besides, we construct examples to provide answers to two closely related questions raised by ErdH{o}s et al.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
