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.
21
questions
2
votes
0answers
48 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 ...
2
votes
1answer
87 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 ...
2
votes
0answers
97 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 ...
2
votes
2answers
121 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....
4
votes
1answer
202 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 ...
9
votes
0answers
102 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$-...
4
votes
0answers
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 ...
5
votes
0answers
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 ...
7
votes
2answers
338 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$....
1
vote
1answer
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 ...
3
votes
0answers
109 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 ...
8
votes
3answers
604 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 $\...
1
vote
2answers
673 views
Upper bound for number of independent sets
What is the tightest upper bound known for the number of independent sets in a graph?
6
votes
0answers
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 \...
5
votes
0answers
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$.
...
2
votes
1answer
344 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 ...
3
votes
0answers
179 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$, ...
4
votes
0answers
101 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 {\...
6
votes
1answer
256 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])$, ...
5
votes
1answer
219 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 ...
8
votes
2answers
281 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 ...
