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

28 questions
Filter by
Sorted by
Tagged with
352 views

### Algorithm to check whether a given set is Sidon

We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct. What algorithms do ...
• 203
126 views

### What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

Treewidth is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$. A natural family of ...
• 9,269
181 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 ...
• 1,242
217 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)$ ...
• 63
86 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 ...
• 716
195 views

• 12.9k
1 vote
824 views

### Upper bound for number of independent sets

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

• 9,448
269 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])$, ...
• 9,448
238 views

### Kruskal-Katona Theorem with Majority?

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