Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUnion-intersecting set systems
399
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We study the basic operation of set union in the global model of differential privacy. In this problem, we are given a universe $U$ of items, possibly of infinite size, and a database $D$ of users. Each user $i$ contributes a subset $W_i subseteq U$ of items. We want an ($epsilon$,$delta$)-differentially private algorithm which outputs a subset $S subset cup_i W_i$ such that the size of $S$ is as large as possible. The problem arises in countless real world applications; it is particularly ubiquitous in natural language processing (NLP) applications as vocabulary extraction. For example, discovering words, sentences, $n$-grams etc., from private text data belonging to users is an instance of the set union problem. Known algorithms for this problem proceed by collecting a subset of items from each user, taking the union of such subsets, and disclosing the items whose noisy counts fall above a certain threshold. Crucially, in the above process, the contribution of each individual user is always independent of the items held by other users, resulting in a wasteful aggregation process, where some item counts happen to be way above the threshold. We deviate from the above paradigm by allowing users to contribute their items in a $textit{dependent fashion}$, guided by a $textit{policy}$. In this new setting ensuring privacy is significantly delicate. We prove that any policy which has certain $textit{contractive}$ properties would result in a differentially private algorithm. We design two new algorithms, one using Laplace noise and other Gaussian noise, as specific instances of policies satisfying the contractive properties. Our experiments show that the new algorithms significantly outperform previously known mechanisms for the problem.
Given a combinatorial design $mathcal{D}$ with block set $mathcal{B}$, the block-intersection graph (BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B} $ are adjacent if and only if $|B_{1} cap B_{2}| > 0$. The $i$-block-intersection graph ($i$-BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B}$ are adjacent if and only if $|B_{1} cap B_{2}| = i$. In this paper several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian $2$-BIGs and result in larger TTSs that also have Hamiltonian $2$-BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian $2$-BIGs (equivalently TTSs with cyclic $2$-intersecting Gray codes) as well as the complete spectrum for TTSs with $2$-BIGs that have Hamilton paths (i.e., for TTSs with $2$-intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel clasess in arbitrary TTSs, and then construct larger TTSs with both cyclic $2$-intersecting Gray codes and parallel classes.
List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t geq k$, a $(k,t)$-list assignment is a list assignment $L$ where $|L(v)| geq k$ for all vertices $v$ and $|L(u)cup L(v)| geq t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.
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
