Questions tagged [extremal-set-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 views

Integral representation of completely alternating homogeneous functionals on semi-lattice of continuous functions

For a long time I've been interested in G. Choquet seminal work "Theory of capacities" (Annales de l’institut Fourier, tome 5 (1954), p. 131-295). More precisely part 53 about integral ...
Vladimir B.'s user avatar
5 votes
1 answer
189 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
  • 18.3k
2 votes
0 answers
77 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
44 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
1 vote
0 answers
120 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 ...
Groups's user avatar
  • 369
2 votes
1 answer
126 views

Turán density of hypergraphs with very few edges

As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
domotorp's user avatar
  • 18.3k
6 votes
1 answer
256 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
110 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
2 votes
1 answer
224 views

Union closed family of sets with at most a certain number of couples of sets with non-empty intersection

Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most: $$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \...
Fabius Wiesner's user avatar
4 votes
1 answer
119 views

On the number of disjoint subsets of a large set families

Let $[n] := \{1,\dots,n\}$, for some large integer $n$, and let $\mathcal{F}$ be a family of 2-element subsets of $[n]$. The famous Erdös-Ko-Rado (EKR) theorem says that if $|\mathcal{F}| > {n - 1 ...
John Hans's user avatar
6 votes
2 answers
385 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
77 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 ...
wandering_lambda's user avatar
1 vote
0 answers
103 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
92 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
0 answers
87 views

Restricted Erdos-Ko-Rado theorem reference

Consider a family $\mathfrak{F}$ of $k$ element subsets of $\{1,2,..,n\}$, where $n\geq 2k$, such that any two members of $\mathfrak{F}$ have nonempty intersection. The Erdos-Ko-Rado theorem asserts ...
Chris H's user avatar
  • 1,854
11 votes
2 answers
594 views

Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond. Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets ...
nonuser's user avatar
  • 237
2 votes
0 answers
58 views

Is the finite projective plane stable as an extremal set system?

Let $\Sigma$ be a set of $|\Sigma| = n$ subsets of the universe $[n]$, each of size $k$, with the property that any two of these subsets intersect on at most one element. It is easy to see that the ...
GMB's user avatar
  • 1,379
1 vote
1 answer
136 views

Number of distinct 3-sets formed as subsets of a 4-uniform set family

Let $\mathcal{F} \subseteq \binom{[n]}{4}$ be a collection of size-4 subsets of $\{1,\ldots,n\}$, i.e., a 4-uniform set family. Let $\mathcal{F'}$ be the collection of size-3 sets for which a ...
Bart Jansen's user avatar
2 votes
1 answer
139 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
3 votes
1 answer
271 views

the size of a down-set?

I'm reading a research article lately, and got confused about a question. So, the fundamental theorem of Kruskal and Katona states that if each set in a given set system $\mathcal{A}$ has $k$ ...
Joseph Stone's user avatar
13 votes
2 answers
354 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
  • 31.5k
5 votes
0 answers
161 views

A Combinatorial Problem on Extremal Set Theory

Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist? (i) $\forall S\in \mathcal{F}$, $|S|=a$....
Zihan Tan's user avatar
  • 151
4 votes
1 answer
214 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
192 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
1 vote
0 answers
194 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=...
Paul Bub.'s user avatar
  • 105
3 votes
0 answers
132 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
  • 22.8k
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
  • 22.8k
6 votes
1 answer
577 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
  • 28.7k
9 votes
0 answers
312 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{...
Francis Raj S's user avatar
2 votes
1 answer
825 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
202 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
417 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
180 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
5 votes
1 answer
247 views

Can a partition free family in $2^{[n]}$ always be enlarged to one of size $2^{n-1}$?

Let $\left[ n \right]=\{{1,2,\cdots,n\}}$ and call a family $\mathcal{F} \subset 2^{\left[n\right]}$ partition-free if it does not contain any partition of $\left[n\right]$. A recent question asked ...
Aaron Meyerowitz'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
17 votes
5 answers
1k views

Optimal bounds for an alternating sum on a downset

Let $n$ be a natural number, and consider the discrete cube $2^{[n]} := \{ A: A \subset \{1,\ldots,n\}\}$ consisting of all subsets of the $n$-element set $[n] := \{1,\ldots,n\}$. Define a downset in ...
Terry Tao's user avatar
  • 108k
4 votes
2 answers
1k views

Cyclic subgroups of finite abelian groups

I learned from MO Subgroups of a finite abelian group that the problem of enumerating subgroups (not up to isomorphism) of finite abelian groups is a difficult one. Are there simple formulas if one ...
user22518's user avatar
4 votes
1 answer
830 views

Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now. The most general ...
Seva's user avatar
  • 22.8k
4 votes
1 answer
2k views

Minimal generation for finite abelian groups

Let $G$ be a finite abelian group. I know of two ways of writing it as a direct sum of cyclic groups: 1) With orders $d_1, d_2, \ldots, d_k$ in such a way that $d_i|d_{i+1}$, 2) With orders that are ...
Calc's user avatar
  • 115
15 votes
1 answer
705 views

The hypercube: $|A {\stackrel2+} E| \ge |A|$?

I have a good motivation to ask the question below, but since the post is already a little long, and the problem looks rather natural and appealing (well, to me, at least), I'd rather go straight to ...
Seva's user avatar
  • 22.8k
3 votes
1 answer
268 views

Lower bounding the maximum size of sets in a set family with union promise

The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and ...
Artem Kaznatcheev's user avatar
14 votes
1 answer
1k views

How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ ...
6 votes
2 answers
457 views

What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?

This problem arose in the study of Latin squares with a large number of subsquares, although it appears interesting in its own right. Question: What is the maximum cardinality of a family $F \...
Douglas S. Stones's user avatar
6 votes
3 answers
506 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
745 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