Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [extremal-combinatorics]

Extremal combinatorics studies how large or how small a collection of finite objects (numbers, graphs, vectors, sets, etc.) can be, if it has to satisfy certain restrictions.

23 questions
Filter by
Sorted by
Tagged with
87 views

1 vote
718 views

### Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
94 views

259 views

### Constructing a k-perfect permutations family

I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, ...
I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
### Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$
Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$. If $n=|V|$， then what is the smallest number of $V(H)$? The number is at most $3n/4$： consider a set of disjoint $4$-holes. Can ...