Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProblems and results on 1-cross intersecting set pair systems
108
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The notion of cross intersecting set pair system of size $m$, $Big({A_i}_{i=1}^m, {B_i}_{i=1}^mBig)$ with $A_icap B_i=emptyset$ and $A_icap B_j eemptyset$, was introduced by Bollobas and it became an important tool of extremal combinatorics. His classical result states that $mle {a+bchoose a}$ if $|A_i|le a$ and $|B_i|le b$ for each $i$. Our central problem is to see how this bound changes with the additional condition $|A_icap B_j|=1$ for $i e j$. Such a system is called $1$-cross intersecting. We show that the maximum size of a $1$-cross intersecting set pair system is -- at least $5^{n/2}$ for $n$ even, $a=b=n$, -- equal to $bigl(lfloorfrac{n}{2}rfloor+1bigr)bigl(lceilfrac{n}{2}rceil+1bigr)$ if $a=2$ and $b=nge 4$, -- at most $|cup_{i=1}^m A_i|$, -- asymptotically $n^2$ if ${A_i}$ is a linear hypergraph ($|A_icap A_j|le 1$ for $i e j$), -- asymptotically ${1over 2}n^2$ if ${A_i}$ and ${B_i}$ are both linear hypergraphs.
rate research
Read More
Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.
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 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.
Mubayis Conjecture states that if $mathcal{F}$ is a family of $k$-sized subsets of $[n] = {1,ldots,n}$ which, for $k geq d geq 2$, satisfies $A_1 capcdotscap A_d eq emptyset$ whenever $|A_1 cupcdotscup A_d| leq 2k$ for all distinct sets $A_1,ldots,A_d inmathcal{F}$, then $|mathcal{F}|leq binom{n-1}{k-1}$, with equality occurring only if $mathcal{F}$ is the family of all $k$-sized subsets containing some fixed element. This paper proves that Mubayis Conjecture is true for all families that are invariant with respect to shifting; indeed, these families satisfy a stronger version of Mubayis Conjecture. Relevant to the conjecture, we prove a fundamental bijective duality between $(i,j)$-unstable families and $(j,i)$-unstable families. Generalising previous intersecting conditions, we introduce the $(d,s,t)$-conditionally intersecting condition for families of sets and prove general results thereon. We conjecture on the size and extremal structures of families $mathcal{F}inbinom{[n]}{k}$ that are $(d,2k)$-conditionally intersecting but which are not intersecting, and prove results related to this conjecture. We prove fundamental theorems on two $(d,s)$-conditionally intersecting families that generalise previous intersecting families, and we pose an extension of a previous conjecture by Frankl and Furedi on $(3,2k-1)$-conditionally intersecting families. Finally, we generalise a classical result by ErdH{o}s, Ko and Rado by proving tight upper bounds on the size of $(2,s)$-conditionally intersecting families $mathcal{F}subseteq 2^{[n]}$ and by characterising the families that attain these bounds. We extend this theorem for certain parametres as well as for sufficiently large families with respect to $(2,s)$-conditionally intersecting families $mathcal{F}subseteq 2^{[n]}$ whose members have at most a fixed number $u$ members.
Let $G$ be a graph, and let $w$ be a positive real-valued weight function on $V(G)$. For every subset $S$ of $V(G)$, let $w(S)=sum_{v in S} w(v).$ A non-empty subset $S subset V(G)$ is a weighted safe set of $(G,w)$ if, for every component $C$ of the subgraph induced by $S$ and every component $D$ of $G-S$, we have $w(C) geq w(D)$ whenever there is an edge between $C$ and $D$. If the subgraph of $G$ induced by a weighted safe set $S$ is connected, then the set $S$ is called a connected weighted safe set of $(G,w)$. The weighted safe number $mathrm{s}(G,w)$ and connected weighted safe number $mathrm{cs}(G,w)$ of $(G,w)$ are the minimum weights $w(S)$ among all weighted safe sets and all connected weighted safe sets of $(G,w)$, respectively. Note that for every pair $(G,w)$, $mathrm{s}(G,w) le mathrm{cs}(G,w)$ by their definitions. Recently, it was asked which pair $(G,w)$ satisfies the equality and shown that every weighted cycle satisfies the equality. In this paper, we give a complete list of connected bipartite graphs $G$ such that $mathrm{s}(G,w)=mathrm{cs}(G,w)$ for every weight function $w$ on $V(G)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
