All Questions
Tagged with co.combinatorics extremal-set-theory
13 questions with no upvoted or accepted answers
9
votes
0
answers
335
views
Families of subsets with pairwise symmetric differences of cardinality at most $k$
Let $X$ be an $n$-element set and $\mathcal{F} \subseteq P(X)$ such that for all $A, B \in \mathcal{F}$, $|A△B| \leq k$ where $A△B$ denotes the symmetric difference of $A$ and $B$. Suppose $|\mathcal{...
8
votes
0
answers
1k
views
The state of art of the sunflower lemma
I am interesting in the sunflower system and its applications in computer science.
Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...
- 393
4
votes
0
answers
114
views
Kruskal-Katona for homocyclic groups?
I need a version of the Kruskal-Katona theorem (better still, of the Lovasz "approximate" version thereof) for the elementary abelian / homocyclic groups, in the following spirit:
What is the ...
- 23k
3
votes
0
answers
124
views
Minimum number of couples of sets with non-empty intersection in a union closed family
Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element ...
- 1,000
3
votes
0
answers
95
views
Minimum number of partitions of a set such that the same pair must occur in a block in at least half of them
For positive integers $k$ and $n$, let ${S} = \{1,\dots,k\ n\}$. Consider $\ell \ge 3$ partitions $P_1,\dots,P_\ell$ of ${S}$, where each $P_i$ splits ${S}$ into $n$ blocks all of size $k$.
Question: ...
- 31
3
votes
0
answers
133
views
Kruskal-Katona for multisets?
Following Fedor Petrov's remarks, here is a "set-theoretic version" of the
question I asked a while ago.
For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite)
multisets with the ...
- 23k
3
votes
0
answers
102
views
What is the maximal number of partitions with this maximal intersection property?
Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...
- 726
2
votes
0
answers
99
views
A variant of the social golfer problem and the kirkman schoolgirl problem
I came across the following simple question that seems to be open:
Let $U$ be a set of $n$ elements.
Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $...
1
vote
0
answers
45
views
How small must partitions be to ensure overlapping blocks?
Consider the set family $F$ of all $t$-element subsets of $[n]$, for some positive integer $n$.
Let $P_1$ be a partition of $F$ into $k$ blocks.
Let $P_2 \ne P_1$ be another partition of $F$ into $k$ ...
1
vote
0
answers
137
views
On a generalisation of the EKR theorem
Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.
Let $C_1\subseteq \mathcal{F}$ be such that any two elements ...
- 379
1
vote
0
answers
79
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
- 135
1
vote
0
answers
104
views
Number of intersections that must occur in any partition of a given size
Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$.
Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...
1
vote
0
answers
204
views
Additional condition to the Bollobas theorem (Sperner's therorem) in extremal set theory
The Bollobas'1965 theorem is the following:
If $A_1,...,A_n$ and $B_1,...,B_n$ are two sequences of subsets of $X=\{1,...,r\}$ such that $A_i\cap B_j = \emptyset$ if and only if $i=j$, then
$$\sum_{i=...
- 105