Difference between revisions of "Open Problems:42"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Partial progress)
(Typo)
Line 28: Line 28:
  
  
'''Update:''' Partial progress has been made in [http://drops.dagstuhl.de/opus/volltexte/2015/5336/ FPS15] where it is proved that if all $k$-discs in $G$ are trees (i.e., $G$ has girth greater than $2k+1$), then $|H| \leq \frac{10^{10^{50}}}{\epsilon}$. The result generalizes to arbitrary degree bound $d$ and $k \geq 0$, and $H$ can be constructed in constant time at the cost of roughly an additional factor $\epsilon^{-1}$. It was sketched by the same authors at the [http://math.ucsd.edu/~sbuss/SPB_Workshops/AlgCPTC_1.html Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics in Moscow in 2016] that one can also construct $H$ if $G$ is planar by using the planar separator theorem. In this case, $|H| \in O(\epsilon^{-4})$.
+
'''Update:''' Partial progress has been made in [http://drops.dagstuhl.de/opus/volltexte/2015/5336/ FPS15] where it is proved that if all $k$-discs in $G$ are trees (i.e., $G$ has girth greater than $2k+1$), then $|V(H)| \leq \frac{10^{10^{50}}}{\epsilon}$. The result generalizes to arbitrary degree bound $d$ and $k \geq 0$, and $H$ can be constructed in constant time at the cost of roughly an additional factor $\epsilon^{-1}$. It was sketched by the same authors at the [http://math.ucsd.edu/~sbuss/SPB_Workshops/AlgCPTC_1.html Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics in Moscow in 2016] that one can also construct $H$ if $G$ is planar by using the planar separator theorem. In this case, $|V(H)| \in O(\epsilon^{-4})$.

Revision as of 17:40, 11 April 2016

Suggested by Noga Alon
Source Bertinoro 2011
Short link https://sublinear.info/42

For a graph $G$, a $k$-disc around a vertex $v$ is the subgraph induced by the vertices that are at distance at most $k$ from $v$. The frequency vector of $k$-discs of $G$ is a vector indexed by all isomorphism types of $k$-discs of vertices in $G$ which counts, for each such isomorphism type $K$, the fraction of $k$-discs of vertices of $G$ that are isomorphic to $K$. The following is a known fact observed in a discussion with Lovász. It is proved by a simple compactness argument.

Fact: For every $\epsilon > 0$, there is an $M=M(\epsilon)$ such that for every $3$-regular graph $G$, there exists a $3$-regular graph $H$ on at most $M(\epsilon)$ vertices (independent on $|V(G)|$), such that variation distance between the frequency vector of the $100$-discs in $G$ and the frequency vector of the $100$-discs in $H$ is at most $\epsilon$.

Question: Find any explicit estimate on $M(\epsilon)$. Nothing is currently known.


Update: Partial progress has been made in FPS15 where it is proved that if all $k$-discs in $G$ are trees (i.e., $G$ has girth greater than $2k+1$), then $|V(H)| \leq \frac{10^{10^{50}}}{\epsilon}$. The result generalizes to arbitrary degree bound $d$ and $k \geq 0$, and $H$ can be constructed in constant time at the cost of roughly an additional factor $\epsilon^{-1}$. It was sketched by the same authors at the Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics in Moscow in 2016 that one can also construct $H$ if $G$ is planar by using the planar separator theorem. In this case, $|V(H)| \in O(\epsilon^{-4})$.