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

26 questions
Filter by
Sorted by
Tagged with
170 views

### Concrete version of KKL Theorem

The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a ...
187 views

### Cover a graph with complete graphs

I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
84 views

### Regularity Lemma for Multi-Relational Graphs?

Is there an analogous to Szemerédi regularity lemma in the setting, where I have multi relational graph i.e. I have $n$ nodes, but instead of having edges to be in $\{0,1\}$ i.e. there is an edge or ...
168 views

1 vote
795 views

### Upper bound for number of independent sets

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

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