Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge non-trivial $t$-intersecting families for signed sets
173
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For positive integers $n,r,k$ with $nge r$ and $kge2$, a set ${(x_1,y_1),(x_2,y_2),dots,(x_r,y_r)}$ is called a $k$-signed $r$-set on $[n]$ if $x_1,dots,x_r$ are distinct elements of $[n]$ and $y_1dots,y_rin[k]$. We say a $t$-intersecting family consisting of $k$-signed $r$-sets on $[n]$ is trivial if each member of this family contains a fixed $k$-signed $t$-set. In this paper, we determine the structure of large maximal non-trivial $t$-intersecting families. In particular, we characterize the non-trivial $t$-intersecting families with maximum size for $tge2$, extending a Hilton-Milner-type result for signed sets given by Borg.
rate research
Read More
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.
A family $mathcal F$ has covering number $tau$ if the size of the smallest set intersecting all sets from $mathcal F$ is equal to $s$. Let $m(n,k,tau)$ stand for the size of the largest intersecting family $mathcal F$ of $k$-element subsets of ${1,ldots,n}$ with covering number $tau$. It is a classical result of ErdH os and Lovasz that $m(n,k,k)le k^k$ for any $n$. In this short note, we explore the behaviour of $m(n,k,tau)$ for $n<k^2$ and large $tau$. The results are quite surprising: For example, we show that $m(k^{3/2},k,tau) = (1-o(1)){n-1choose k-1}$ for $taule k-k^{3/4+o(1)}$. At the same time, $m(k^{3/2},k,tau)<e^{-ck^{1/2}}{nchoose k}$ if $tau>k-frac 12k^{1/2}$.
A hypergraph $mathcal{F}$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $mathcal{F}$. Mubayi and Verstra{e}te showed that for every $k ge d+1 ge 3$ and $n ge (d+1)n/d$ every $k$-graph $mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d ge k ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m ge 4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.
The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate supersaturation extensions, which in this context ask for the minimum number of disjoint pairs that must appear in families larger than the extremal threshold. We study the minimum number of disjoint pairs in families of permutations and in $k$-uniform set families, and determine the structure of the optimal families. Our main tool is a removal lemma for disjoint pairs. We also determine the typical structure of $k$-uniform set families without matchings of size $s$ when $n ge 2sk + 38s^4$, and show that almost all $k$-uniform intersecting families on vertex set $[n]$ are trivial when $nge (2+o(1))k$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
