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
4
votes
1
answer
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 ...
- 1,242
3
votes
1
answer
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)$ ...
- 63
2
votes
1
answer
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 ...
- 706
0
votes
1
answer
168
views
On structure of graphs with average degree equal to maximum average degree
For a simple graph $G$, the $\text{average-degree}(G)=|E(G)|/|V(G)|$ and
the maximum average degree $\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$.
If $\text{...
- 1,703
5
votes
1
answer
231
views
Computational complexity of Turán-type problems
According to Turán's theorem (with $r=n/2$), any graph $G$ with $n$ vertices and at least $n(n-2)/2$ edges must contain a clique of size $n/2+1$. My question is: how hard is it to find this clique?$^*$...
- 223
5
votes
1
answer
254
views
$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)
I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes.
The problem asks to use randomized rounding and first ...
- 1,058
2
votes
1
answer
93
views
"Parity testing set" for disjoint pairs of sets
I'd like a construction of the following description. Let $V$ be a set of $n$ elements. I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there ...
- 803
2
votes
0
answers
107
views
$k$-XOR collision free families
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:
$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor ...
- 9,428
2
votes
2
answers
139
views
On the coloring number of small graphs with small cliques
Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i....
- 475
4
votes
1
answer
270
views
Which (almost) balanced Boolean function has smallest "total" influence
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
- 41
9
votes
0
answers
138
views
Graphs with minimal-size induced subgraphs
I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
- 8,786
4
votes
0
answers
98
views
How to construct an $(n,m,k)$ ``separating set''?
This problem is probably known under some other name, if anyone has seen it before, a reference will be great.
Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary ...
- 9,428
5
votes
0
answers
104
views
Constructing a large bit-vector set with the following property
I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property:
$$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$
In ...
- 9,428
7
votes
2
answers
349
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$....
- 437
1
vote
1
answer
104
views
reference request- property of subset of rows in a matrix
I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
- 11
3
votes
0
answers
110
views
On number of disjoint sets with small stack depth in a set of permutations
Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is ...
- 31
8
votes
3
answers
635
views
Constant in Komlos conjecture
Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\...
- 12.7k
1
vote
2
answers
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?
- 155
6
votes
0
answers
96
views
Perfect hashing family variation - injectivity on $r$ disjoint sets
We denote by $[t]$ the set $\{1,2,\ldots,t\}$.
A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \...
- 9,428
5
votes
0
answers
106
views
What is the smallest deterministic construction of an ordered perfect hashing family?
A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$.
...
- 9,428
2
votes
1
answer
486
views
Upperbound the order of P3-free partition of P4-free graphs
A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free ...
- 1,443
3
votes
0
answers
183
views
Building a "balanced" universal set
A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
- 9,428
4
votes
0
answers
104
views
Constructing a small (n,k)-Covering Matrices family
Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$.
We call ${\cal A}$ a (n,k)-covering, if for every subset of columns
$I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {\...
- 9,428
6
votes
1
answer
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])$, ...
- 9,428
5
votes
1
answer
236
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 ...
- 656
8
votes
2
answers
289
views
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 ...
- 2,560