### Arboricity is different from degeneracy:
- "A classic bound on the degeneracy asserts that $\alpha(G)\leq \sqrt{2m}$ (Lemma 1 of [12])."
[12] is related to the arboricity!
The degeneracy $\alpha$ is the maximum of the minimum degree of any subgraph.
The arboricity $\beta$ is the minimum number of forests needed to cover all edges in the graph.
In [12], $\beta\leq ceil(\sqrt{2m+n})/2$ is proven.
We have, $\beta \leq \alpha \leq 2 \beta − 1$.
- "By a theorem of Chiba-Nishizeki [12], we can argue that the number of vertices in any set of the Turan shadow is at most $\sqrt{2m}$ (where $m$ is the number of edges in G)."
We can actually state that the number of vertices in any set of the Turan shadow is at most $\alpha$ where $\alpha$ is the degeneracy of the input graph (in large and sparse real-world graphs we generally have $\alpha<<\sqrt{2m}$).
### Tight bound on the shadow size:
"Indeed, we can design instances where Claim 5.7 is tight (a set of $n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$."
It is not clear why this is a tight bound. $\alpha$ is the degeneracy of the input graph (the graph "$n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$" may not have degeneracy $\alpha$).
### Scalability of an enumeration procedure:
"The primary challenge is combinatorial explosion. An autonomous system network with ten million edges has more than a trillion 10-cliques. Any enumeration procedure is doomed to failure."
The fact that there can be "a trillion 10-cliques" may not be enough to discard an enumeration procedure. For instance, the program (counting from 1 to one trillion) generated by the following C code terminates within few minutes on a commodity machine.
```c
main() {
unsigned long long i=0;
while (i ＜ 1e12) {
i++;
}
}
```
### Minors:
- "Denote the number of k-cliques by $C$, then the success probability is $C/{ n \choose k}$. Thus, we can estimate this probability using ${ n \choose k}/C$ samples."
This may need some explanations.
### Typos:
- "It will be convenient to express this result in terms on k-clique densities."
### Arboricity is different from degeneracy:
- "A classic bound on the degeneracy asserts that $\alpha(G)\leq \sqrt{2m}$ (Lemma 1 of [12])."
[12] is related to the arboricity!
The degeneracy $\alpha$ is the maximum of the minimum degree of any subgraph.
The arboricity $\beta$ is the minimum number of forests needed to cover all edges in the graph.
In [12], $\beta\leq ceil(\sqrt{2m+n})/2$ is proven.
We have, $\beta \leq \alpha \leq 2 \beta − 1$.
- "By a theorem of Chiba-Nishizeki [12], we can argue that the number of vertices in any set of the Turan shadow is at most $\sqrt{2m}$ (where $m$ is the number of edges in G)."
We can actually state that the number of vertices in any set of the Turan shadow is at most $\alpha$ where $\alpha$ is the degeneracy of the input graph (in large and sparse real-world graphs we generally have $\alpha<<\sqrt{2m}$).
### Tight bound on the shadow size:
"Indeed, we can design instances where Claim 5.7 is tight (a set of $n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$."
It is not clear why this is a tight bound. $\alpha$ is the degeneracy of the input graph (the graph "$n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$" may not have degeneracy $\alpha$).
### Scalability of an enumeration procedure:
"The primary challenge is combinatorial explosion. An autonomous system network with ten million edges has more than a trillion 10-cliques. Any enumeration procedure is doomed to failure."
The fact that there can be "a trillion 10-cliques" may not be enough to discard an enumeration procedure. For instance, the program (counting from 1 to one trillion) generated by the following C code terminates within few minutes on a commodity machine.
```c
main() {
unsigned long long i=0;
while (i ＜ 1e12) {
i++;
}
}
```
### Minors:
- "Denote the number of k-cliques by $C$, then the success probability is $C/{ n \choose k}$. Thus, we can estimate this probability using ${ n \choose k}/C$ samples."
This may need some explanations.
### Typos:
- "It will be convenient to express this result in terms on k-clique densities."
Comments: