Skip to main content

All Questions

Filter by
Sorted by
Tagged with
2 votes
1 answer
142 views

Bounds for ground set of Steiner system (inverse EKR style problem)

Imagine we have $r$ subsets of a ground set $S$, each of size $k$, such that each set of size $l$ is contained in at most one of the $r$ sets. What can we say about the minimum value of $|S|$? I am ...
Tuatarian's user avatar
5 votes
1 answer
221 views

How many base elements can a sunflower-free system have?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdős and Rado says that there is a constant $C_t$ such ...
domotorp's user avatar
  • 19.1k
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 $...
SetFamilyStudent's user avatar
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$ ...
SetFamilyStudent's user avatar
6 votes
1 answer
277 views

A Sauer-Shelah-like lermma for prefix tree

I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known. Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
Or Meir's user avatar
  • 419
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 ...
Fabius Wiesner's user avatar
6 votes
2 answers
392 views

Coloring of a graph representing the power set

For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S_1,S_2 \in \mathcal{P}$, the edge $(S_1,S_2)$ exists ...
wandering_lambda's user avatar
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 ...
wandering_academic's user avatar
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: ...
Arun's user avatar
  • 31
2 votes
1 answer
144 views

Abundance in union closed families

For any finite set $S$ and every partition $S_1, \dots, S_n$ of $S$, let $P(S_1, \dots, S_n)$ be the family consisting of all possible unions of $S_1, \dots, S_n$. Clearly, $P(S_1, \dots, S_n)$ is a ...
Sisyphus's user avatar
13 votes
2 answers
374 views

Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B $

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered ...
Tony Huynh's user avatar
  • 32.1k
4 votes
1 answer
220 views

Maximal number of perfect matchings that pairwise form a Hamiltonian cycle

Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle. Question: Is it true that $MH(...
Daniel Soltész's user avatar
8 votes
1 answer
1k views

On a result of Frankl and Wilson

In the paper 'Intersection theorems with geometric consequences' (Combinatorica 1981) P. Frankl and R. M. Wilson consider families $\mathcal{F}$ of $k$-subsets of $\{1,\dots,n\}$ with the restriction ...
Fedor Petrov's user avatar
2 votes
1 answer
197 views

Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement: If $n \leq 4$ is a natural number, if $\mathcal{F}$ is a union-closed family of non-empty sets, if the universe of $\mathcal{F}$ (i.e. ...
Panurge's user avatar
  • 1,215
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 ...
Seva's user avatar
  • 23k
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 ...
Seva's user avatar
  • 23k
6 votes
1 answer
613 views

Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...
David White's user avatar
  • 30.3k
2 votes
1 answer
877 views

Combinatorics-the maximum number of subsets with a given property

Let $X$ be a set with $n$ elements. I would like to know the maximum number of subsets of $X$ such that the number of elements in the symmetric difference between any two of these subsets is at most $...
Francis Raj S's user avatar
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 ...
JeremyKun's user avatar
  • 726
3 votes
1 answer
215 views

Minimal family of k-sets containing all t-sets

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member ...
Or Meir's user avatar
  • 419
12 votes
2 answers
425 views

Set system with different differences

What is the maximal number of sets in a set system $\mathcal{A}$ of subsets of an $n$ element set such that for every $i \neq j $ and $A_i,A_j \in \mathcal{A}$ the difference $A_i \setminus A_j$ is ...
Daniel Soltész's user avatar
0 votes
1 answer
181 views

Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...
Felix Goldberg's user avatar
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 ...
WangYao's user avatar
  • 393
6 votes
3 answers
511 views

Partitioning the 3-sets of [n]={1,...,n} into families

Let $F_1,...,F_m$ be a partition of the 3-element subsets of $[n]$ into families such that no three subsets in any one family $F_i$ are all contained in one 4-element subset of $[n]$. What is the ...
Moti Novick's user avatar
7 votes
1 answer
774 views

Upper bound for the size of a $k$-uniform $s$-wise $t$-intersecting set system

Given integers $n \geq k \geq t \geq 1$ and an integer $s$, let $m(n,k,s,t)$ denote the maximum size of a family $\mathcal F$ of $k$-subsets of $[n]$, i.e. $\mathcal F \subseteq \binom{[n]}{k}$, such ...
Hung Q. Ngo's user avatar