# WG multi-cops paper plan

## Deadlines

- Larger changes by 12 noon on Thursday 16th
- Small bugfixes/typos done by 9am Monday 20th
- Will submits 5pm Monday 20th

## Plan

All big changes by noon on Thursday. People read through and only make small changes after that, but before 9am Monday. 9am Monday Will takes what we have, and puts it into LNCS and starts putting things into appendices. No one else make changes directly, instead send Will an email with requested changes.

### What goes into the appendix

Preferably list these in some sort of order

## Tasks

### Tasks to assign

### Jess
- **Done** Introduction by noon on Thursday
- **Done** Conclusion by noon on Thursday
- **Done (by someone else? (sorry, WP just wrote that in. - Thanks!))** update below (p 21 green previously)
- Treewidth has a known relationship with cop number: in particular, S&T use the helicopter variant of cops and robbers and show that the helicopter cop number of a graph is equal to ... We do not use this helicopter variant here.
- Prints out PDF at noon on Thursday, reads what she can

### Will

#### Before noon Thursday
- **Done** Finish off tweaks to proof of Lemma 6.7 - cop number of cops-bane graph
- **Done** Use multi-layer consistently
- **Done** Use treewidth (no hyphens) consistently
- **Done** (unless people have more ideas) Add simple results to end of Section 2

#### Monday 20th
- 9am, start putting it into LNCS and moving into appendices
- Submit by 5pm
- Re-read on Tuesday morning for errors

### John
- **Done** get rid of underscore Ds - change to 3-parameter notation
- **Done** Binomial random graph section by Thursday noon
- **Not Done, sorry** Related work?
- **What is this? if relating to Random graph then done** New lower bound bit by Thursday noon

# Things to discuss

- The conclusion section is SUPER long, is that intentional? I am starting to get quite worried about the LNCS page limit.
* JS I have condensed the recap bit and slightly reworded the questions (old one is commented out)

- We define **k** = (k_1, ..., k_tau) as an allocation in our notation section, and use it to define our problems, but never use **k** in the rest of the paper but instead always say "allocation" as a full word.
* WP in favor of leaving as is.
* JS - same though it is a bit weird.

# Resolved things

- Binomial random graphs, Theorem 5.8. The statement says "n ≥ 1" but the proof often says "for large n". Which is it?
* JS The fact the result only holds for large n is given by the $o(e^{-\sqrt{n}})$ etc. I would be happy to just delete the $n\geq 1$ it is just in the past I have been told off for not stating all the variables etc.
* I think having "n ≥ 1" is misleading. I've tried writing it again without mentioning "n ≥ 1". **Done**

- Theorem 5.8 again, the proof says "partition" often but I don't think that's what we want, as we don't want/need the layers to partition our graph. If this is just abusing terminology, then I don't like it as for WG I think they'll expect a partition to be a real partition.
* JS agree but cant remember what we decided for this type of cock up, please change to prefered notion.
* WP: Working on fixing this up. Last inappropriate uses of partition are just in the upper bound of Theorem 5.8, see below **Done**

- Theorem 5.8 again again :)
* WP: We don't clearly state why each layer is connected when doing our sampling. If $p > \ln n / n$ then almost surely they will be connected (do we need a citation?). From the theorem we have $n^{1/2+\varepsilon} ≤ np$ which (I hope) gives $n^{1/2 - \varepsilon} ≤ p$ and thus $p$ is clearly bigger than $\ln n / n$.
* WP: For the upper bound, the proof is still correct if the layers aren't connected, but I wanted to avoid saying "partition". Instead, $G_{n,p}$ is connected - do we just need to say that each layer of $\mathcal{G}$ is exactly $G_{n,p}$ (rather than a partition)? I don't think this breaks anything. **Done this**
* WP: For the lower bound, the bounding of $p^*$ means $p^*$ is also bigger than $\ln n / n$. Should we mention this? Just something like "Note the bound on p from the theorem statement ensures that each sampled graph will be connected." **Done this**
* JS I forgot to add this sorry! Thanks for doing this, I tried to add a more detailed reference but could not find one that gives the exact prob I want $o(e^{-\sqrt{n}})$ although I am nearly certain this does hold. I might add a short proof.
* WP So I know wikipedia is not a reliable source of information, but it does state that log n / n is a sharp threshold for connectedness of G_n,p - https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model .. oooh I see.
* Yes this is true, however I want it to hold with prob $1- e^{-\sqrt n}$ not just w.h.p.. I have now added a proof of this from base principals (Lemma 5.10) so we should be good to go! Thanks for spotting this!
* WP Have you read through it and are okay with it yet?
* I have just finished reading though the new lemma and old proof now and I think it is **Done**
* P.s. I thought that putting $0\leq p\leq 1$ in the statement of Theorem 5.8 was weird if we dont also menton what $n$ is so I have taken this out and just specified n and p more clearly in the start of the section.

- "Simple graph" vs "single-layer graph" vs "(single-layer) graph", also "(single-layer) cop number" and "(single-layer) cops and robbers".
* WP doesn't like the brackets - "single-layer cops and robbers" makes sense and we can add a clarification sentence in the notation section
* JS Simple has a concrete meaning in graph theory we should not abuse it, similarly I saw a "regular" somewhere to mean single layer and removed it. I don't care what is done with brackets.
* WP Regular being mis-used is bad, but yeah simple does have a specific meaning, and all our "single-layer" graphs are actually simple graphs so it's at least a well-known definition. I think maybe a quick "As we discuss multi-player cops and robbers as well as cops and robbers played on simple graphs, we will use single-layer graphs to mean simple graphs, and then use single-layer cops and robbers to mean cops and robbers played on simple graphs (and similarly for terms like cop number)."
* WP Standardised on "single-layer graphs" and "single-layer cops and robbers" etc, with one sentence in notation explaining this

- Motivation of "global robber" idea, the text mentions "the robber not having an unfair advantage"
* WP doesn't like talking about an "unfair advantage" because that really seems ambiguous. Can just drop that sentence and start with "A setting that appears often"
* JS sure

- Just after Lemma 5.1, "The definition and lemma above give simple to check criteria ..."
* WP thinks simple is misleading. It's definitely not computationally "simple" i.e. tractable.
* JS I did not mean simple to compute, just not hard to get head around. This is just a bit of careless chat separating two lemmas, feel free to change
* WP Rephrased to avoid saying simple to check

- Chatter around definition of minimum degree in multi-layer graphs (Just after Lemma 5.3)
* WP still thinks we should be clearer that we are making up this definition, because it reads like this is an established definition already and it really isn't. Happy to leave discussion as-is though.
* JS I have changed the text before it to indicate that it is a new parameter.
* WP Looks good to me

- Section 6.1. I get that our graphs have O(N log N) vertices and cop number at least omega(N).
* WP: Are we sure that translates exactly to n vertices and theta(n / log n) cop number? It felt right at first glance, but when I sit down and try to work out intermediate steps I don't get anywhere near this.
* JS the direction we really care about (\Omega bit) is super easy: N\log N =n , thus N < n (large n) so N = n/\log N > n/\log n. I cannot even see in the paper where we claim that it is \Theta(..)?? If we do we dont need to as nobody cares about the upper bound on that specific graph. Either way, here is the idea for the O() part: N=n/\log N = n/(\log n - \log\log N)\leq n/(\log n - \log\log n) < 2n/\log n when n is sufficently large. It is a bit less clean to do this formally but still elementary, this is why I left it out.
* WP: Yup, that makes sense. And yeah, Omega not theta, sorry!

- Section 6.1. We often state $\alpha > 0$, but rarely the $\alpha \leq 1$ part.
* WP: Is there a reason to not always give both bounds?
* Resolved

- Conclusion
* WP: Should we mention the possibility of multi-layer cops and robbers being useful for investigating interesting parameters for multi-layer graphs, the way cops and robbers is useful for treewidth etc.
* JS yeh why not if we can write something nice
* WP: have added a sentence for this

# Things not in paper that can be looked at for a journal version, don't do now!

- If R is a tree, and layers are connected, then mc(G) ≤ 2. If R is also a subset of some cop layer, then mc(G) = 1. However, it's O(tau^2) to work out if 2 cops can win in general, as you check every pair of layers for a robber's edge
- Using a clustered 2-coloring of the line graph (max deg 4) of a three regular expander we can come up with a 2-edge-colouring of the expander such that each monochromatic component of edges has bounded size. This can then replace the 3-edge-colouring in the proof of Theorem 6.1, giving the same lower bound but usng one less cop layers.