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
0
votes
1
answer
87
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,603
5
votes
1
answer
225
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?$^*$...
- 213
5
votes
1
answer
237
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 ...
- 680
2
votes
1
answer
90
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
105
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,358
2
votes
2
answers
129
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....
- 455
4
votes
1
answer
224
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
109
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$-...
- 7,350
4
votes
0
answers
97
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,358
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,358
7
votes
2
answers
339
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
96
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
617
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.5k
1
vote
2
answers
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?
- 155
6
votes
0
answers
94
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,358
5
votes
0
answers
105
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,358
2
votes
1
answer
377
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,423
3
votes
0
answers
182
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,358
4
votes
0
answers
102
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,358
6
votes
1
answer
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])$, ...
- 9,358
5
votes
1
answer
223
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
286
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,530