Return to Question

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the conditions:

1. for every pair of points $p_i,p_j$ for $i,j\in\{1,\dots,n\}$ with $i\neq j$ there is a $k\in\{1,\dots,m\}$ such that $i,j\in\mathcal I_k$ holds.

2. number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

My problem is what is the worst case $m$ do I need?

 

Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the conditions:

1. for every pair of points $p_i,p_j$ for $i,j\in\{1,\dots,n\}$ with $i\neq j$ there is a $k\in\{1,\dots,m\}$ such that $i,j\in\mathcal I_k$ holds.

2. number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

My problem is what is the worst case $m$ do I need?

Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the condition:

number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

1. My problem is what is the worst case $m$ do I need?

2. Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the conditions:

1. for every pair of points $p_i,p_j$ for $i,j\in\{1,\dots,n\}$ with $i\neq j$ there is a $k\in\{1,\dots,m\}$ such that $i,j\in\mathcal I_k$ holds.

2. number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

My problem is what is the worst case $m$ do I need?

Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ pairwise disjoint index sets $\mathcal I_1,\dots,\mathcal I_m$ that are subsets of $\{1,\dots,n\}$ whose union is $\{1,\dots,n\}$ on the condition:

number of facets in convex hull of points in each index set is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

1. My problem is what is the worst case $m$ do I need?

2. Does $m=polylog(d)$ hold if $d=polylog(n)$ holds?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the condition:

number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

1. My problem is what is the worst case $m$ do I need?

2. Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?