# Questions tagged [extremal-set-theory]

The extremal-set-theory tag has no usage guidance.

**6**

votes

**2**answers

233 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
...

**2**

votes

**0**answers

36 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 ...

**1**

vote

**1**answer

77 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 ...

**2**

votes

**1**answer

99 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 ...

**3**

votes

**1**answer

203 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$ ...

**12**

votes

**2**answers

257 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 ...

**3**

votes

**0**answers

95 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$....

**4**

votes

**1**answer

79 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 $...

**8**

votes

**1**answer

371 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 ...

**2**

votes

**1**answer

144 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. ...

**1**

vote

**0**answers

149 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=...

**3**

votes

**0**answers

107 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 ...

**4**

votes

**0**answers

94 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 ...

**6**

votes

**1**answer

304 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 ...

**9**

votes

**0**answers

200 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{...

**2**

votes

**1**answer

196 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 $...

**3**

votes

**0**answers

92 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 ...

**3**

votes

**1**answer

159 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 ...

**12**

votes

**2**answers

356 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 ...

**0**

votes

**1**answer

141 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$ ...

**5**

votes

**1**answer

194 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 ...

**7**

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 ...

**15**

votes

**5**answers

955 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 ...

**4**

votes

**2**answers

856 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 ...

**4**

votes

**1**answer

558 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 ...

**3**

votes

**1**answer

1k 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 ...

**15**

votes

**1**answer

588 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 ...

**3**

votes

**1**answer

243 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 ...

**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

391 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 \...

**7**

votes

**1**answer

503 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 ...