Open Problems:42 - Revision history

Krzysztof Onak at 16:27, 10 December 2016

2016-12-10T16:27:03Z

89.109.239.35: Typo

2016-04-11T17:40:13Z

Typo

89.109.239.35: Partial progress

2016-04-11T17:38:48Z

Partial progress

Krzysztof Onak: updated header

2013-03-07T01:54:27Z

updated header

Krzysztof Onak: Created page with "{{Header |title=Graph Frequency Vectors |source=bertinoro11 |who=Noga Alon }} For a graph $G$, a $k$-disc around a vertex $v$ is the subgraph induced by the vertices that are ..."

2012-11-17T03:41:26Z

Created page with "{{Header |title=Graph Frequency Vectors |source=bertinoro11 |who=Noga Alon }} For a graph $G$, a $k$-disc around a vertex $v$ is the subgraph induced by the vertices that are ..."

New page

{{Header
|title=Graph Frequency Vectors
|source=bertinoro11
|who=Noga Alon
}}
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.

← Older revision		Revision as of 16:27, 10 December 2016
Line 27:		Line 27:
	currently known.		currently known.

		+	== Updates ==

−	~~'''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})$.	+	Partial progress has been made by Fichtenberger et al. {{cite\|FichtenbergerPS-15}}, who 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$. $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})$.

← Older revision		Revision as of 17:40, 11 April 2016
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})$.

← Older revision		Revision as of 17:38, 11 April 2016
Line 26:		Line 26:
	'''Question:''' Find ''any'' explicit estimate on $M(\epsilon)$. Nothing is		'''Question:''' Find ''any'' explicit estimate on $M(\epsilon)$. Nothing is
	currently known.		currently known.
		+
		+
		+	'''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})$.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Noga Alon