wip

Graphs

A (simple) graph $G$ is a set, $V(G)$ of verticies, and $E(G)$: two element subsets of $G$, known as edges.

A sequence of vertices, with edges between subseqent verticies, is called a walk. If Each edge is unique (but a vertex may repeat) we call it a trail (there are some other names), if each vertex is unique, we call it a path. Finally, if we have a path, and take an edge from the last vertex to the first vertex, we have what is called a cycle.

let $x,y \in V(G)$. we say $x$ is connected to $y$, if there exists a path from $x$ to $y$ in $G$. Indeed, the relation induced on $V(G)$ is an equivalence, and partions $V(G)$ into connected “subgraphs” (as defined below) such that any edge has both endpoints in exactly one connected component.

For two graphs $G,H$ we say $H$ is a subgraph of $G$, if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$.

A subgraph of $G$ can be induced by:

Selecting a subset $U$ of $V(G)$, and taking all edges in $G$ with both endpoints in $U$. We call such subgraphs vertex induced.

Selecting a subset $X$ of $E(G)$, and taking the verticies of endpoints. We call such subgraphs edge induced.

We claim that if $G$ is connected, then $G$ has at least $|V|-1$ edges.

we will induct on $n$, being the number of verticies, $n=1, n=2$ are obvious, suppose the hypothesis holds when $k \leq n$

Take any connected graph on $n+1$ vertices, and remove $v_{n+1}$, Then, let $C_{1},C_{2},\dots C_{r}$ be the connected components of the resulting graph. let $C_{i}$ have $k_{i}$ vertices, by our hypothesis, $C_{i}$ has at least $k_{i}-1$ edges. Further, there must be at least 1 edge from $v_{n+1}$ into each connected component. Thus, the total number of edges is at least $\sum_{i=1}^r(k_{i}-1) + r = n$. Closing the induction

The handshaking lemma says, if you count the degree of each vertex, you count each edge twice, (once for each endpoint), thus

$$\sum_{v}d(v) = 2|E(G)|$$

A coloring of the verticies of a graph, is a map $\phi: V(G) \to [r]$ where $r$ is the number of colors being used. we say a coloring is valid if whenever $uv \in E(G)$ $\phi(u) \neq \phi(v)$.

The chromatic number of a graph, written $\chi(G)$, is the smallest $r$ for which there exists a valid coloring with $r$ colors.

its easy to give an uppoer bound on $\chi(G)$ based on the maximum degree of a vertex in $G$, often denoted $\Delta(G)$.

We claim $\chi(G) \le \Delta(G) + 1$, of course, any vertex $v$ is adjacent to atmost $\Delta(G)$ other vertices. Arrange the verticies of $G$ in any order say $v_{1},v_{2},\dots v_{n}$. We shall construct a coloring of $V(G)$ inductively. set $\phi(v_{1}) = 1$. Suppose you can color $v_{1},v_{2},\dots v_{i}$ with at most $\Delta(G)+1$ colors. $v_{i+1}$ is only adjacent to at most $\Delta(G)$ vertices, even if all of them were colored distinctly so far, we have (at least) one extra color we can use to color $v_{i+1}$.

Moreover, whenever $H$ is a subgraph of $G$, we have $\chi(H) \leq \chi(G)$. (simply inherit the coloring to $H$).

For a given graph $H$, the number $ex(n,H)$ is the maximum number of edges you can put on an $n$ vertex graph, such that it does not contain $H$ as a subgraph, In problems of this flavor, $H$ is called the forbidden graph.

Suppose only $\chi(H) = c$ is known. well, we know that for any $n$, the complete $c-1$ partite graph, with nearly equal vertices in each part, has lots of edges, and can be colored with $c-1$ colors. But $H$ cannot be colored with fewer than $c$ colors, so This graph avoids $H$ as a subgraph.

But as we will show later, The complete $c-1$ partite graph, with nearly equal verticies in each part, is actually the best we can do, when $H$ is the complete graph on $c$ vertices.

Suppose $n$ is large, of all the candidates of $H$ with $\chi(H) = c$, $K_{c}$ is the densest candidate, in the sense that its got as little vertices and as many edges as possible. Just thinking of it in a back of the napkin way, avoiding $K_{c}$ means avoiding him in all $c$ sized subgraphs, of which there may be many, so you’d be removing a lot of edges.

Now,, suppose $H$ is connected, and $\chi(H) = c$, and $|V(H)| = c+1$. Now suppose $K_{c} \leq H$. That means some $v_{c+1}$ in $H$ has an edge into $K_{c}$, but $d(v_{c+1}) < c$ otherwise, we would have $H = K_{c+1}$. That is, $H$ is less dense than $K_{c+1}$. We shall get into such ideas later, let us develop some machinery first.

Let $G$ be a graph, $U \subset{ V(G) }$ is known as an independent set, if the vertex induced subgraph by $U$ has no edges.

we can therefore say that $G$ is $r$-colorable, if and only if there exists a partition of $V(G)$ into at most $r$ independent sets.

This is obviously true, as any valid coloring $\phi: V(G) \to [r]$ has for each $i$, $\phi^{-1}(i)$ to be an independent set. On the other hand, if one produces a partition of $V(G)$ into sets $V_{1},V_{2},\dots V_{k}$ where $k \le r$ and each $V_{i}$ is an independent set, we may construct a valid coloring $v \mapsto i \iff v \in V_{i}$.

Let $A \subseteq V(G)$ be an independent set. We say that $A$ is full if each $v \in V(G)\setminus A$ has some $u \in A$ for which $uv$ is an edge. (Such a set is usually called a maximal independent set.)

On the other hand, suppose there exists $v^* \in V(G)\setminus A$ for which there is no $u \in A$ such that $uv^*$ is an edge. Then, $A \cup \{v^*\}$ is an independent set with strictly more elements.

This means that if $A$ is an independent set of maximum size, then $A$ is full.

We claim that the converse is not true. For example, take the complete bipartite graph $K_{5,10}$. The part with five vertices and the one with 10 vertices are both full, but only the part with 10 vertices has maximum size.

Now, we shall relate this to the chromatic number.

let $A \subseteq V(G)$ be an independent set, then $\chi(G) \le 1 + \chi(G[V(G)\setminus A])$ where $G[V(G)\setminus A]$ is the subgraph induced by $V(G)\setminus A$ (you could color $A$ with just 1 new color).

Now we feel as though, if $A$ is a maximum independent set, then $\chi(G) = 1+ \chi(G[V(G)\setminus A])$, and indeed, it is enough to show one coloring of $G$ with $\chi(G)$ colors, where one color class is a maximum independent set.

We will give a counter-example: A graph $G$ where no optimal coloring has a maximum independent set:

In the above graph, we see there is only one maximum independent set, namely $v_{1},v_{4},v_{5}$ (notice that any other 3-subset has at least one edge internally) but if $v_{1},v_{4},v_{5}$ are all colored the same, the internal triangle must use 3 new colors.

An optimal coloring is shown below. credit (https://math.stackexchange.com/questions/684077/graph-colouring-and-maximal-independent-set?__cf_chl_tk=fjeZiqSBC8CuG8sZaGfTGVZp84frS5LZdqvxnsZgwT0-1789336237-1.0.1.1-ls3XYRVWjPuJ6EE_9a1Glx8UKBd9tUtia3PJWpH6.uk)

What is true, is that if $\phi : V(G) \to [\chi(G)]$, is a valid coloring, each color class $\phi^{-1}(i)$ has some $x_{i}$ with at least one edge into every other color class.

Suppose for the contrary, that any $x \in \phi^{-1}(1)$ has some $j$ for which, $x$ has no edge into $\phi^{-1}(j)$. In this case, we may color $x$ with the color $j$. Doing this for each $x \in \phi^{-1}(1))$, we obtain a coloring of $V(G)$ with at most $\chi(G)-1$ colors, which is impossible.

We now take a small detour:

For each $k,r,s$, There exists some $N(k,r,s)$ such that if the complete $s$-uniform hypergraph (meaning every hyper-edge is an s-element subset) on $N$ verticies is edge-colored with $r$ colors, There is a monochromatic complete $s$-uniform hypergraph on $k$ verticies as a subgraph.

Notationally, we denote the complete $s$ uniform hypergraph on $n$ vertices as $K(n,s)$.

proof: Let $N$ be sufficently large, and color any $s$-edge in $K(N,s)$ one of $r$ colors, with uniform probability.

Now take some subgraph $V$ induced by a vertex set of size $k$. Indeed, $V= K(k,s)$ (upto isomorphism). Now, what is the probability of $V$ being monochromatic in edges?

There are $\binom{k}{s}$ edges, each of them must be the same color, ie the probability of $V$ being monochromatic in a particular color is $r^{-\binom{k}{s}}$. Thus,

$$\mathbb{P}\bigl(V \text{ is monochromatic}\bigr) = r^{1-\binom{k}{s}}$$

Now, let $N = tk$ for some sufficently large $t$. We know that (due to inclusion-exclusion) The probability that some subgraph $K(k,s)$ is monochromatic is at least the probability of one of many disjoint subgraphs, each isomorphic to $K(k,s)$ being monochromatic.

That is, Let $R$ denote the probability that $K(N,s)$ when is colored with $r$ colors, has a monochromatic copy of $K(k,s)$.

we have

$$R \ge t r^{1-\binom{k}{s}}$$

Now suppose $t \geq r^{\binom{k}{s} - 1}$. Then it follows that $R = 1$, And thus, since every coloring of $K(N,s)$ has a non zero probability, it must be that every coloring of $K(N,s)$ contains a monochromatic copy of $K(k,s)$.

We shall re-visit traingle free graphs:

Let $G = (V,E)$ be a triangle free graph. And $v \in V$ a vertex with maximum degree, Let $|V| = n$.

Then, $Y =adj(v)$ is an independent set, (where $adj(v)$ is all the vertices with an edge to $v$). Thus, every edge has at least one endpoint in $X =V - adj(v)$.

Thus $|E| \leq \sum_{x\in X} d(x) \le |X||Y| \le (|X| + |Y|)^2/4 =n^2/4$

Where the last inequality follows from $AM-GM$, and thus, the sharp point tells us something about constructing the extremal triangle free graph. The AM-GM reaches equality when both numbers are equal.

That is, we know that the extermal graph has two roughly equal parts, and all edges are between these two parts.

Ie the extremal graph that is triangle free, is the complete bipartite graph with nearly equal parts.

Below, we have the most beautiful exercise. (1.1.3 in zhao’s book) Let $X,Y$ be random vectors drawn independently from the same distribution on $\mathbb{R}^d$. prove that:

$$\mathbb P(|X+Y| \ge 1) \ge \frac{1}{2} \mathbb P(|X| \ge 1)^2$$

Graphs, Ramsey, Groups

A group $G$ is a groupoid of one object (indeed, a groupoid is a category where every morphism is an isomorphism).

this is mostly a quip

we say $g \in G$ has finite order, if for some $n \in \mathbb{N}$, $g^n = e$. The smallest such $n$ we call the order of $g$, usually denoted $|g|$. If no such $n$ exists, we say that the order of $g$ is infinite.

The order of the whole group, is the cardinality of the underlying set, denoted $|G|$.

suppose $|g|$ is finite, then for any $n$ for which $g^n = e$, $|g|$ divides $n$. since $n \ge |g|$, we have $n = q|g| + r$, where $0 \le r < |g|$

that is, $g^{q|g|}g^r = e$. Obviously, it follows that $g^r = e$, if $r \neq 0$, we contradict the minimality of $|g|$, thus proving our claim.

The above claim is an equivalence, if $g$ is finite order, then for any $n \in \mathbb{Z}$, $g^n = e$ if and only if $n = p|g|$, for some integer $p$.

It is important to note that cancellation holds in groups on both sides, ie $ah = bh \implies a =b$ and $ha = hb \implies a = b$ (the reverse directions obviously hold in both cases for any $h \in G$)

A group $G$ is abelian (or commutative) if for any $x,y \in G$ we have $xy = yx$. Usually, we use additive notation and write the identity element as $0_{G}$ where $G$ is commutative.

the notation $x^n$ giving $x$ operated with itself $n$ times, gets replaces by $nx$ in an abelian group, of course $n \in \mathbb{Z}$ may not be an element of $G$ in any sense. and if $n$ is negative, we mean operating the inverse of $x$, $n$ times.

even if $n \neq m$ we may have $na = ma$, (it may very well be that $(m-n)a$ is the identity or what not.

ex 1.3 , suppose $G$ is a group such that for each $g \in G$, $g^2 = e$, ie $|g| = 2$, when $g \neq e$. We claim $G$ is abelian.

let $u = xy$, for any $x,y \in G$. we have $xu = y$, and thus $x = yu$ and further $yx = u$. Proving our claim. The converse direction does not hold, for example $\mathbb{Z}, +$ is abelian, and there is no $x \in \mathbb{Z}$ other than $0$ for which $x +x = 0$.

Now you may tell me, if $G$ is both finite and abelian, then we may get the property $g^2 = e$ for each $g \in G$.

well, consider the group of $\mathbb{Z}/n\mathbb{Z}$, with addition of congruence classes modulo $n$. From our earlier discussion, we know that this group is well defined inheriting the operator $[x]{n}[y]{n} : = [x + y]_{n}$ if any only if $n\mathbb{Z}$ is a normal subgroup. It certainly is a subgroup, adding two multiples of $n$ gives you another multiple of $n$, so it is closed after inheriting addition from $\mathbb{Z}$.

is $n\mathbb{Z}$ normal? well, we want to show that $x + n\mathbb{Z} -x = n\mathbb{Z}$ for any $x \in \mathbb{Z}$, which follows immediately as $\mathbb{Z}$ is abelian.

Okay, this was just me instilling enough structure. It is clear that $\mathbb{Z}/n\mathbb{Z}$ is abelian, but if $n > 2$ for example, $[1]{n} + [1]{n} = [2]{n} \neq [0]{n}$.

So finite group order along with commutativity does not guarentee that elements have order atmost $2$.

if $G$ is himself of finite order, we claim that every $g \in G$ has finite order, and $|g| \le |G|$.

well, consider $g^0 = e, g^1, g^2,\dots g^{|G|}$, These are $|G| + 1$ products, thus they are not all distinct. ie there exists $0 \le i < j \le |G|$ for which $g^j = g^i$, but of course then $g^{j-i} = e$, this must mean that $|g|$ is finite, and divides $j-i$, which is a positive quantity, and of course $|g| \le j-i \le |G|$.

We will eventually build to the theorem, that claims that if $G$ is of finite order, the order of each element divides the order of $G$.

At this point, Allufi (my homie) says, the order of group elements don’t necessarily play nice with the operator, that is, you could have $x,y \in G$, both of finite order, but $|xy| = \infty$ or “your favourite natural number” (his words not mine). And asks us to work out exercise 1.12

ex1.12, In the group of invertible $2\times{2}$ matrices with real entries, let

$$g = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}, \qquad h = \begin{bmatrix} 0 & 1 \\ -1 & -1 \end{bmatrix}$$

we must verify that $|g| = 4, |h| = 3$ and $|hg| = \infty$.

We we treat them as linear maps, $g: (x,y) \mapsto (-y, x)$, $h: (x,y) \to (y, -(x+y))$ (I ask the reader to to recall that matricies describe linear maps, and matrix multiplication is map composition)

ie $hg$ is the composed linear map $h \circ g$, therefore $hg : (x,y) \to (-y,x) \to (x,y-x)$.

Now, notice under repeated application of $g$ (flip co-ordinate, negate the first one) we have:

$$\begin{aligned} (x,y) \to (-y,x) \to (-x,-y) \to (y,-x) \to (x,y) \end{aligned}$$

Similarly for $h$:

$$\begin{aligned} (x,y) \to (y, -(x+y)) \to (-(x+y),x) \to (x,y) \end{aligned}$$

ie $|g| = 4$ and $|h| = 3$

now, look at $hg = k$. it takes $(x,y) \to (x, y-x)$. If you were to apply $k$ again, you would see $(x,y) \to (x, y-2x)$. Thus we inductively show that $k^n : (x,y) \to (x,y-nx)$, which can never be the identity linear map, showing the desired result.

Moving in the line of “one cant really say too much about the order of products”, we will say little things.

let $g \in G$ be an element of finite order. What can we say about the order of $g^m$ for some $m \in \mathbb{N}$? we know that it is finite.

the order of $g^m$ is the smallest number $r$ for which $g^{mr} = e$, that is $mr$ is the smallest multiple of $m$, such that the above equation holds. As seen earlier, $mr$ is also a multiple of $|g|$.

Conversely, any multiple of both $m$ and $|g|$, call it $mq$, has the property that $g^{mq} = e$.

Thus, $mr$ is the smallest such number, ie $mr = \operatorname{LCM}(m,|g|)$

that is:

$$|g^m| = \frac{\operatorname{LCM}(m,|g|)}{m} = \frac{|g|}{\operatorname{GCD}(m,|g|)}$$

Now, let $g,h \in G$ be elements of finite order, such that they commute, ie $gh = hg$.

let $x$ be a common multiple of $|g|, |h|$. Notice, $(gh)^x = g^xh^x$ holds, as $gh = hg$. Thus, $(gh)^x = e$.

ie the order of $gh$ is finite, and in particular, we can choose $x = \operatorname{LCM}(|g|,|h|)$. Thus, we have $|gh|$ divides $\operatorname{LCM}(|g|, |h|)$.

Naturally: ex 1.13 Give an example where $g,h$ commute, but $|gh|$ is not equal to $\operatorname{LCM}(|g|,|h|)$.

The multiplication table of a group, basically puts the operator relation into a table.

For a finite set $S$, say $|S| = n$, firstly we see that for elements of $S$ to be actually unique, we can’t have the same $s$ appearing twice on each row or each column.

Otherwise, we have $s_{i}s = s_{j}s$ and since groups have cancellation $s_{i} = s_{j}$, or $ss_{j} = ss_{i}$ and hence $s_{j} = s_{i}$.

so, it is clear that every element appears eactly once in each row and each column. Further, electing $s_{1}$ to be the identity, the appearance of $s_{1}$ is symmetric across the diagonal. (perhaps on the diagonal)

we claim that for $n \le 3$ there is only one multiplication table up to relabeling.

Well, electing $s_{1}$ to be the identity, the first row is $(s_{1},s_{2},\dots s_{n})$, we may identify it with the identity permutation $id$ on $[n]$.

Well, every other row, must be a distinct permutation on $[n]$ without fixed points. (the permutation on the first row has all fixed points)

counting permutations with no fixed points is sometimes called the hat-check problem.

let there be $n$ people. $p_{1}$ receives some hat $h_{i}$ that is not his own. Where, $p_{i}$ owns the hat $h_{i}$.

now, there are two disjoint cases, either $p_{i}$ recives $h_{1}$, in which case, we have the equivalent problem with $n-2$ people and $n-2$ hats, or $p_{i}$ recieves some other hat. There are $h-1$ hats remaining, (nobody else can recieve $h_{i}$). On top of that, $p_{i}$ can’t recieve $h_{1}$. Remove $p_{1}, h_{1}$ and relabel $p_{i},h_{i}$ to $p_{1}, h_{1}$. Thus this is equivalent to the problem with $n-1$ people and $n-1$ hats.

ie $D_{n} = (n-1)(D_{n-1} + D_{n-2})$ where $D_{0} = 1, D_{1} = 0$. Solving the reccurence gives us

$$D_{n} = n!\sum_{i=0}^n\frac{-1^i}{i!}$$

$D_{4} = 9$ so clearly this is not forcing in any way. But we will still leave the discussion in.

if $n=1$, we have the trivial group, if $n = 2$, we have $s_{1},s_{2}$ for which $s_{2}^2 = s_{1}$.

if $n = 3$, write $S = e,a,b$. we have $a^2 \neq a$, thus $a^2 = b$ and similarly, $b^2 = a$, which must mean that $ab = ba = e$.

notice in this group, $|a| = |b| = 3$, but $|ab| = 1$. Thus provoiding an example for ex1.3.

so all finite groups of order at most $3$ are uniquely determined up to isomorphism, and are abelian.

ex1.14 says, lets $g,h$ be elements of a group with finite order, $|g|,|h|$ are co-prime, and $g,h$ commute. we are to show that $|gh| = |g| |h|$.

we know that $|gh|$ divides $\operatorname{LCM}(|g|,|h|)$, since $\operatorname{GCD}(|g|,|h|) = 1$, we have $|gh|$ divides $|g||h|$.

now suppose $(gh)^t = e$. then, $g^t = (h^{-1})^t$ therefore, $g^{t|h|} = e$. that is $|g|$ divides $t|h|$, but of course $|g|,|h|$ are co-prime, therefore $|g|$ divides $t$.

Similarly, ${h^{-1}}^{t|g|} = e$, so $|h|$ divides $t|g|$, and hence $|h|$ divides $t$. Again, since $|h|,|g|$ are co-prime, $|g||h|$ divides $t$. Select $t = |gh|$, thus showing $|g||h| = |gh|$.

ex1.8 Let $G$ be a finite group with exactly one element $f$ of order $2$. Show that $\prod_{g \in G} g = f$. (Allufi in my text misses that $G$ must be abelian, I was crying for a bit as to how one can define THE product independent of order, but all is well :))

Let $G = { g_{1},g_{2},\dots g_{n}}$ where $g_{1} = e$ and $g_{2} = f$.

Due to the cancellation law in groups, (or however you wish to argue) each $g_{i}$ has a unique inverse $g_{f(i)}$ with no collisions, that is, if $f(i) = f(j)$ then $i = j$.

Now we shall argue that if $i \ge 3$, $f(i) \ge 3$. clearly $f(i) \neq 1$, as this would make $g_{i} = e$. Suppose $f(i) = 2$. then $g_{i}g_{2} = e$, thus, $g_{i} = g_{2}$, as $g_{2}$ has order 2. But of course,$i \ge 3$, again a contradiction.

thus $\prod_{i=1}^n g_{i} = g_{2} \prod_{i=3}^ng_{i}$ but of course, due to abelianity, we can pair $g_{i}$ with $g_{f(i)}$ in the product (this also implies $n$ is even btw) and thus we have the desired result.

The above exercise cleanly preceeds the next one

ex1.9, Let $G$ be a finite group of order $n$, which exactly $m$ order-2 elements. Show that $n-m$ is odd, and thus deduce that if $n$ is even there must be some order-2 element in $G$.

From the exercise above, we know that (excluding $e$) the other elements are either order $2$ or order at least $3$. we further know that those with order at least $3$ have inverses of order at least $3$, and that if $g$ is an order at-least 3 element $g^{-1}\neq g$.

That is to say, $G$ is partitioned (one partition may be empty) into $e$, the $m$ two order elements, (whose inverse are themselves) and the remaining elements must be even, pairing up with inverses.

Ie $n = 1 + m + 2r$ for some $r \ge 0$. Thus, $n-m$ is odd. And it follows directly that if $n$ is even, $m$ is odd, and thus $m \ge 1$.

ex1.10: Suppose order of $g$ is odd, what can you say about $|g^2|$?

$$|g^2| = \frac{|g|}{\operatorname{GCD}(2, |g|)}$$

but of course, $|g|,2$ are co-prime. thus $|g^2| = |g|$.

ex1.11 Show that for all $g,h \in G$, $|gh| = |hg|$

suppose $|x| = |axa^{-1}|$, (for any $x,a \in G$) then we would get $|gh|= |h(gh)h^{-1}| = |hg|$.

Now we must show that $|x| = |axa^{-1}|$.

Notice $(axa^{-1})^n = ax^na^{-1}$. That is, $(axa^{-1})^n = e \iff ax^na^{-1} = e \iff x^n = e$.

1.15 let $G$ be a commutative group, and $g$ be an element of maximal finite order. That is, if $h \in G$ has finite order $|h| \le |g|$. Prove that if $h \in G$ has finite order, $|h|$ divides $|g|$.

The hint uses prime factorization. thus, we shall develop some number theory.

let for $a,b \in \mathbb{Z}$: $S = \{ax + by > 0 : x,y \in \mathbb{Z}\}$ Due to the well ordering principle (owing to the fact that $S$ is non empty, with either $a$ or $-a$ in it, $S$ has a minimum element $d = ax_{0}+by_{0}$. by euclids lemma, $a = dq + r$ where $0 \leq r < d$.

ie $r = a- qax_{0} -qby_{0}$. ie $r = a(1-qx_{0}) + b(qy_{0})$ since $r<d$, this contradicts the minimality of $d$, thus, it must be that $r = 0$. That is, $d|a$. With a similar argument using $b$, we have $d|b$. thus put togeather, $gcd(a,b)|d$. But again, since $d$ is minimal, $d = gcd(a,b)$. In general, whenever $d$ is a multiple of $gcd(a,b)$ we can construct solutions.

Moreover, the fact that $gcd(a_{1},a_{2},\dots a_{n}) = gcd(gcd(a_{1},\dots a_{n-1}),a_{n})$ along with induction can show that $\sum a_{i}x_{i} = k$ has integer solutions if and only if $k$ is a multiple of $gcd(a_{1},a_{2},\dots a_{n})$, and any multiple will do.

in particular, $gcd(a,b) = 1$ if and only if $ax + by = 1$ has a solution.

Chinese remainder theorem:

Now, let $N = \prod_{i=1}^n a_{i}$, where any two $a_{i},a_{j}$ are co-prime. Select any integers $x_{1},x_{2},\dots x_{n}$. The system of equations $z \equiv x_{i} \pmod{a_{i}}$ has a solution, moreover, any two solutions are congruent modulo $N$. We will prove the existance of a solution first.

We shall induct on $n$. for $n = 2$, we know that since $gcd(a_{1},a_{2}) = 1$ we have $1 = u_{1}a_{1} + u_{2}a_{2}$. Set $z = x_{2}u_{1}a_{1} + x_{1}u_{2}a_{2}$

We have, $z = x_{2}u_{1}a_{1} + x_{1}(1-u_{1}a_{1})$ obtaining $z \equiv x_{1} \pmod{a_{1}}$, and similarly, $z \equiv x_{2} \pmod{a_{2}}$.

Now, suppose the existance part of the theorem holds for some $n-1$, let $z$ be solution of the first two equations, replace it with a single equation, $z \equiv T \pmod{a_{1}a_{2}}$. Clearly, any $a_{i}$ for $i \ge 3$ is still co-prime with $a_{1}a_{2}$, as $a_{i}$ is pairwise co-prime with $a_{1}$ and $a_{2}$. Thus, there is a solution to these $n-1$ equations. Thus colsoing the induction.

Now we shall show uniqueness upto modulo $N$.

if $z,z'$ are both solutions to the system, we have $a_{i}| z'-z$ for each $i$, since the $a_{i}$‘s are pairwise co-prime, this means $\prod_{i=1}^na_{i}|(z'-z)$ that is, $z \equiv z' \pmod{N}$.

Another way to look at this is, take some classes $[x_{i}]{a{i}}$

In particular, we are interested in $\phi: \mathbb{N} \to \mathbb{N}$, $\phi(n) = \lvert\{x < n : \operatorname{GCD}(x,n)=1\}\rvert$. This map is called Euler’s totient.

Notice, that $p$ is a prime, then $\phi(p) = p-1$. let $p,q$ be primes, and $x < pq$. Then, either $p|x$ or $q|x$ or $gcd(x,pq)=1$. Of course then, we must remove the multiplies of $p$: $p,2p, \dots (q-1)p$ and the multiples of $q$: $q,2q, \dots (p-1)q$. That is, $\phi(pq) = pq -(q-1) - (p-1) -1 = (p-1)(q-1) = \phi(p)\phi(q)$. This of course assumes that $p\neq q$.

Now, $\phi(p^k) = p^k - (p^{k-1})$. next, we show that the totient is multiplicative, that is whenever $a,b$ are co-prime, $\phi(ab) = \phi(a)\phi(b)$.

let $A = \{x < a : \operatorname{gcd}(x,a) = 1\}$, $B = \{y < b : \operatorname{gcd}(y,b)=1\}$, and $AB = \{z < ab : \operatorname{gcd}(z,ab) = 1\}$.

we shall construct a bijection from $A \times B$ to $AB$.

Measure

We will first develop some needed set theory:

First, recall that unions distribute over intersections and vice versa.

Now, let $A_{1},B_{1} \subset{ U_{1} }$ and $A_{2}, B_{2} \subset{ U_{2} }$.

We have the following:

$$(A_{1}\times A_{2}) \cap (B_{1} \times B_{2}) = (A_{1} \cap B_{1}) \times (A_{2}\cap B_{2})$$ $$(A_{1} \cup B_{1}) \times (A_{2} \cup B_{2}) = \ (A_{1}\times A_{2}) \cup (A_{1} \times B_{2}) \cup (B_{1}\times A_{2}) \cup (B_{1} \times B_{2})$$ $$(A_{1}\times A_{2})^c = (A_{1}^c \times U_{2}) \cup (U_{1} \times A_{2}^c)$$

Which follow easily from elementary set theory. Using induction we get:

Let $A_{i,j}\subseteq U_i$ for $i=1,\ldots,n$ and $j=1,\ldots,k_i$.

$$\prod_{i=1}^n\left(\bigcap_{\alpha=1}^{k_i} A_{i,\alpha}\right).$$ $$\bigcup_{(j_1,\ldots,j_n)\in\prod_{i=1}^n \{1,\ldots,k_i\}} \prod_{i=1}^n A_{i,j_i}.$$

If $U=\prod_{i=1}^n U_i$, then

$$\bigcup_{i=1}^n \prod_{j=1}^n B_{i,j},$$

where

$$B_{i,j}= \begin{cases} A_i^c, & j=i,\\ U_j, & j\neq i. \end{cases}$$

note: the reason we are being anal about which universe are these sets in, is to ensure taking unions and intersections happen in the same land, and products are subsets of the products of the underlying universe, nevertheless we will mostly deal with $\mathbb{R}$, $\mathbb{R}^d$ being the universe.

We call a set $I = \langle a, b \rangle$, where $a\le b \in \mathbb{R}$, an interval. (The notation is meant to unify half open, open and closed intervals.) The measure of an interval $|I|$ is defined to be $b-a$. In particular, this means that the measure of a point, and the empty set, are both zero.

Let $E = \bigcup_{i=1}^T J_{i}$ be a finite union of intervals, we claim that $E$ can be partitioned into disjoint intervals: write the endpoints of each $J_{i}$ in increasing order (ignoring repetitions). that is, we have

$$x_{1} < x_{2} < \dots x_{m}$$

where each $x_{j}$ is one of the endpoints of some $J_{i}$.

Thus, we make make disjoint intervals $I_{p}$, $1 \le p \le m$, where each $I_{p}$ is either an open interval $(x_{i}, x_{i+1})$ or the point $x_{i}$ as the interval $[x_{i},x_{i}]$.

Clearly, each $J_{i}$ is a union of some subcollection of $I_{1},I_{2},\dots I_{m}$. Thus, $E$ is a finite union of disjoint intervals.

we call the collection $I_{1},I_{2},\dots I_{m}$ a refinement of $J_{1},J_{2},..J_{T}$.

we say $B \subset{ \mathbb{R}^d }$ is a box, if it a cartesian product of intervals. Suppose $B = \prod_{j=1}^d I^j$. Then we define the measure of $B$, $|B| := \prod_{j=1}^d |I^j|$.

Let $E = \bigcup_{k=1}^T B_k$ be a finite union of boxes. We claim that $E$ can be partitioned into finitely many disjoint boxes.

Let $B_k = \prod_{j=1}^d I^j_k$.

Now, for each $1 \leq j \leq d$, let $J^j_1,J^j_2,\dots,J^j_{m^j}$ be a refinement of $I^j_1,I^j_2,\dots,I^j_T$.

That is, each $I^j_k$ is the disjoint union of some subcollection of $J^j_1,J^j_2,\dots,J^j_{m^j}$.

Now for each $r=(r_1,r_2,\dots,r_d)\in\prod_{j=1}^d[m^j]$, consider the product

$$P(r)=\prod_{j=1}^d J^j_{r_j}.$$

If $r\neq r'$, then $r$ differs from $r'$ in at least one coordinate, say $j$. In that case $J^j_{r_j}$ and $J^j_{r'_j}$ are disjoint. Thus, $P(r)$ and $P(r')$ are disjoint.

Finally, since each $I^j_k$ is a union of some of the $J^j_r$, each $B_k$ is a union of some of the $P(r)$. Hence $E$ is a union of some of the $P(r)$, so these $P(r)$ give the desired partition of $E$.

to get an intuition of the proof, look at the above picture, here the thick boxes are $B_{1},B_{2},B_{3}$ in $\mathbb{R}^2$ the region between each vertical dashed line is a refinement of the $x$-intervals, and between the horizonatal dashed lines, a refinement of the $y$-intervals. thus every little box, is a product of refined intervals, clearly, not all such products are actually in one of $B_{1},B_{2},B_{3}$, but we can pick those that are.

Awesome! this will come in handy (wink wink the measure of $E$ will be sum of the measures of each part in a partition of $E$, and we will also show that two different partitions of $E$ will still have the same sum, though this is intuitively clear)

let $B,C$ be boxes, we claim that $B \cap C$ is a finite union of boxes. The proof follows from noticing that we can take the intersection co-ordinate wise, and the intersection of two intervals is a (possible empty) interval. The product with the emptyset is empty, which is a box.

Now, we claim that $B\setminus C$ is a box. First, notice that $B\setminus C = B \cap C^c$. Let $B = \prod_{j=1}^dI_{j}$ and $C = \prod_{j=1}^dK_{j}$

As we have seen above, $C^c = \bigcup_{i=1}^d\prod_{j=1}^d X_{i,j}$, where $X_{i,j} = \mathbb{R}$ when $i\neq j$ and $X_{i,j} = K_{j}^c$ when $i=j$.

That is,taking co-ordinatewise intersection, after distribution the intersection over the unions

$$B\setminus C = \bigcup_{i=1}^d \prod_{j=1}^d (I_{j} \cap X_{i,j})$$

. But $I_{j} \cap \mathbb{R} = I_{j}$ Thus,

$$B\setminus C = \bigcup_{i=1}^d \left(\prod_{j=1}^{i-1}I_{j} \times (I_{i}\cap K_{i}^c) \times \prod_{j=i+1}^d I_{j}\right)$$

but $I_{i} \cap k^c_{i}$ is a finite union of intervals. A consequence of the start of the notebook, is that we can allow the reader to convince themselves that this union can be distributed out.. OKAY FINE I’LL WRITE IT BUT JUST ONCE.

Let $I_{i} \cap K^c_{i} = \bigcup_{x=1}^p V^i_{x}$

write

$$B\setminus C = \bigcup_{i=1}^d (S^i \times (\bigcup_{x=1}^pV^i_{x}) \times Q^i)$$

Since, cartesian products are associative (upto isomorphism) we get (distributing the union over the product)

$$B\setminus C = \bigcup_{i=1}^d\left((\bigcup_{x=1}^p(S^i \times V^i_{x})) \times Q^i\right)$$

I WARNED YOU IT GETS UGLY. do it again, and we have

$$B\setminus C = \bigcup_{i=1}^d \bigcup_{x=1}^p(S^i \times V^i_{x} \times Q^i)$$

Indeed, $S^i \times V^i_{x} \times Q^i$ is a box, thus $B\setminus C$ is a finite union of boxes.

if $E \subset{ \mathbb{R}^d }$ is a finite union of boxes, we call $E$ an elementary set.

Let $E,F$ be elementary sets, where $E = \bigcup_{k=1}^T B_{k}$, $F = \bigcup_{s=1}^R C_{s}$. Of course, $E \cup F$ is an elementary set.

Notice

$$E \cap F = \bigcup_{s=1}^R \bigcup_{k=1}^T (B_{k} \cap C_{s})$$

As shown earlier, the intersection of two boxes, is a box. Thus $E \cap F$ is elementary.

Now, we will unfortunately give a multi-line series of equalities.

$$\begin{aligned} E\setminus F &= E \setminus \bigcup_{s=1}^R C_{s} \\ &= \bigcap_{s=1}^R (E\setminus C_{s}) \\ &= \bigcap_{s=1}^R \bigcup_{k=1}^T (B_{k}\setminus C_{s}) \end{aligned}$$

But we have already establised that the difference of two boxes is a finite union of boxes, And is thus elementary. Moreover, we have established that the finite union and finite intersection of elementary sets are elementary. Thus $E\setminus F$ is elementary.

Moreover, The symmetric difference $E \Delta F = (E\setminus F) \cup (F\setminus E)$ is elementary, so is the translation $x + E := \{x+e : e \in E\}$ (the translation of a box is a box)

Now, we shall measure an interval $I$ by counting (with normalization) the number of tighter and tighter grid points that land in it.

let $I = \langle a, b\rangle$. we claim that

$$b-a = \lim_{ n \to \infty } \frac{1}{n} \#(I \cap \frac{\mathbb{Z}}{n})$$

where $\#$ denotes the cardinality of finite sets, and

$$\frac{\mathbb{Z}}{n}:= (\frac{z}{n}: z \in \mathbb{Z})$$

well, since $I$ is bounded, let $x_{n},y_{n}$ be the smallest and largest integers (respectively) for which $x_{n}/n, y_{n}/n \in I$.

Thus, we have ${x_{n}/n, (x_{n}+1)/n, \dots y_{n}/n} = I \cap \frac{\mathbb{Z}}{n}$ writing $x_{n}/n = a_{n}, y_{n}/n = b_{n}$

we have ${a_{n}, a_{n} + (1/n), a_{n} + (2/n), \dots, b_{n}} = I \cap \frac{\mathbb{Z}}{n}$ ie, $\#(I \cap \frac{\mathbb{Z}}{n}) = n(b_{n}-a_{n}) + 1$

Thus,

$$\frac{1}{n}\#(I \cap \frac{\mathbb{Z}}{n}) = b_{n}-a_{n} + \frac{1}{n}$$

oh how nice would it be, if $b_{n}$ converges to $b$ and $a_{n}$ converges to $a$, given that $1/n$ converges to $0$, we can just do arithmetic on these limits! (they exist after all)

due to the minimality of $a_{n}$ and maximality $b_{n}$, we have $a_{n} - \frac{1}{n}, b_{n} + \frac{1}{n} \not \in I$. Thus,

$$a_{n}- \frac{1}{n} \le a \le a_{n}, \ b_{n} \le b \le b_{n} + \frac{1}{n}$$

Rearranging we get:

$$0 \le a_{n} -a \le \frac{1}{n}, \ \ 0 \le b-b_{n} \le \frac{1}{n}$$

Ie for any $\epsilon > 0$, whenever $n > \lceil \frac{1}{\epsilon} \rceil$ we have $|a-a_{n}| < \epsilon$ and $|b-b_{n}| < \epsilon$.

Thus, proving the desired result.

let $B = \prod_{j=1}^d I_{j}$ be a box, by definition, $|B| = \prod_{j=1}^d |I_{j}|$.

Thus,

$$|B| = \prod_{j=1}^d \lim_{ n \to \infty } \frac{1}{n} \#(I_{j} \cap \frac{\mathbb{Z}}{n})$$

since each limit exists, and is non negative, (not sure non negativity is needed btw) and the product is finite, we have

$$|B| = \lim_{ n \to \infty } \frac{1}{n^d} \prod_{j=1}^d \#(I_{j} \cap \frac{\mathbb{Z}}{n})$$

but of course, the product of cardinalities, is the cardinality of the cartestian product.

Thus,

$$|B| = \lim_{ n \to \infty } \frac{1}{n^d} \#(B \cap \frac{\mathbb{Z}^d}{n})$$

Now, let $E$ be an elementary set, take any partition $E = \bigsqcup_{k=1}^T B_{k}$

Now, notice (again allowing interchanging a finite sum of limits that exist)

$$\sum_{k=1}^T |B_{k}| = \lim_{ n \to \infty } \frac{1}{n^d} \sum_{k=1}^T\#(B_{k} \cap \frac{\mathbb{Z}}{n})$$

but of course, the sum of the cardinalities of a collection of disjoint sets, is the cardinality of their union

thus,

$$\sum_{k=1}^T |B_{k}| = \lim_{ n \to \infty } \frac{1}{n^d} \#(E \cap \frac{\mathbb{Z}}{n})$$

Notice that the right hand side is independent of the choice of partition of $E$. Thus we define, the measure of an elementary set:

$$m(E) := \lim_{ n \to \infty } \frac{1}{n^d} \#(E \cap \frac{\mathbb{Z}}{n})$$

Indeed, the measure of an elementary set, is the sum of the measure of boxes that partition it.

Let $E_{i}$, $1 \le i \le T$ be a pairwise disjoint collection of elementary sets. It is clear (by choosing a partion of each $E_{i}$ into boxes) that

$$m(\bigcup_{i=1}^T E_{i}) = \sum_{i=1}^T m(E_{i})$$

This property is called finite additivity.

Now, notice, if $E,F$ are elementary, we have $m(E) = m(E\setminus F) + m(E \cap F)$ and $m(F) = m(F\setminus E) + m(E \cap F)$. But $E \cup F = (E\setminus F) \cup (F\setminus E) \cup (F \cap E)$ where all three sets are disjoint.

Thus, we have $m(E\cup F) = m(E) + m(F) - m(E \cap F)$. This is called inclusion exclusion. It follows that

$$m(\bigcup_{i=1}^TE_{i}) \le \sum_{i=1}^Tm(E_{i})$$

for any finite finite collection of elementary sets (not necerssaririly all disjoint)

Now, let $E \subseteq F$, notice $F = E \cup (F\setminus E)$, a union of disjoint sets, thus, $m(E) \le m(F)$. This property is called monotonicity.

Now, notice that $m(E) = m(x +E)$ where $x+E$ is the translation of $E$ by $x$. (This is easily shown by writing $E$ as a disjoint union of boxes, and noticing that the measure of each box is translationally invariant).

And of course $m(\emptyset) = 0$.

Now, we have the weakest notion possible, of “measurable” sets, (and their measure) namely the elementary sets. we saw that the above measure $m$ had certain properties, we will say that any function assigning non neative real numbers to the elementary sets, with all the properties that $m$ has, is a measure of elementary sets. And we will study it.

let $\mathscr{E}(\mathbb{R}^d)$ be the collection of elementary sets in $\mathbb{R}^d$ and $v: \mathscr{E}(\mathbb{R}^d) \to \mathbb{R}^+$ be a map. We say $v$ is a measure of elementary sets if:

$v(\emptyset) = 0$. The measure of the empty set is $0$ under $v$.

if $E,F$ are disjoint, $v(E \cup F) = v(E) + v(F)$ (finite additivity).

if $E \subseteq F$, $v(E) \le v(F)$ (monotonicity)

for any $x \in \mathbb{R}^d$, $v(x + E) = v(E)$ (translational invarience).

note: the property $v(E \cup F) \le v(E) + v(F)$ for not necesearilly disjoint $E,F$, is called finite sub-additivity, and follows from 2. and 3.

We shall now prove certain things about any $v$, that is a measure of elementary sets.

let $x \in \mathbb{R}^d$ be any point, seen as a box with all equal endpoints, we claim $v(x) = 0$.

Suppose for the contrary that there is some $x^*$ for which $v(x^*) = a > 0$. Then, due to translational invarience, for each $x \in \mathbb{R}^d$, we have $v(x) = a$.

now, consider for each $n \in \mathbb{N}$, $n$ points in $[0,1]^d$. Due to finite additivity, and monotonicity (again treating each of these points as boxes with equal endpoints), we get $na \le v([0,1]^d)$, implying that $v([0,1]^d)$ is not defined.

Now, let $E \subseteq F$, then we claim $v(F\setminus E) = v(F) - v(E)$. (left as an exercise for the reader,due to its obvious nature)

Now, we pause, and ponder about the nature of certain arguments we’ve been making, a lot of it involves growing or shrinking of nice sets and taking limiting measures.

Let $\mathscr{U}$ be a universal set, then we may form the subset category, $\mathscr{P}(\mathscr{U})$ whose objects are (any) subsets of $\mathscr{U}$ and morphisms are $A \to B$ (at most one between any two objects) if $A \subseteq B$, or the superset category $\mathscr{P}(\mathscr{U})^{op}$ where a morphism $A \to B$ means $B \subseteq A$.

Both of these are poset categories, where the identity means $A \subseteq A$, and composition depicts the transitive nature of inclusion.

Indeed, an infinite sequence of inclusions, $A_{1} \subseteq A_{2} \subseteq \dots$, or dually $A_{1} \supseteq A_{2} \supseteq \dots$,

is a functor from $\mathbb{N}_{<}$ (as an order category) to $\mathscr{P}(\mathscr{U})$ or $\mathscr{P}(\mathscr{U})^{op}$ respectively.

since we are considering All subsets of $\mathscr{U}$, the categorical co-limit of any such functor, exists and is equal to $\bigcup_{n \in \mathbb{N}}A_{n}$, the countable union, in $\mathscr{P}(\mathscr{U})$ and is equal to $\bigcap_{n \in \mathbb{N}} A_{n}$, the countable intersection in $\mathscr{P}(\mathscr{U})^{op}$.

That is to say, That the countable union, and countable intersection, act as the least upper bound of the objects of such a functor, in their respective categories.

A clean way to look at it is: In $\mathscr{P}(\mathscr{U})$, for any collection of objects, $\mathcal{A} = \{A_{\alpha} : \alpha \in I\}$, its least upper bound and greatest lower bound exist (the greatest lower bound may be the empty set) and are given by $\bigcup_{\alpha \in I}A_{\alpha} = \sup \mathcal{A}$ and $\bigcap_{\alpha \in I} A_{\alpha} = \inf \mathcal{A}$.

Form the order category $\mathscr{E}^d =(\mathscr{E}(\mathbb{R}^d), \subseteq)$ of elementary sets in $\mathbb{R}^d$, among other things, a measure $v$ is a monotonic map to $\mathbb{R}^+$, it is thus a functor from $\mathscr{E}^d \to (\mathbb{R}^+, \le)$.

Now let $a: \mathbb{N} \to \mathbb{R}$ be a non decreasing sequence that is bounded above. we claim that $\lim_{ n \to \infty } a_{n} = \alpha =\sup(a(\mathbb{N}))$. (An analog can be given for non increasing sequences that are bounded below)

Suppose $a$ is eventually constant, then obviously, that constant must be $\alpha$. That is, $a$ is eventually constant if and only if $\alpha \in a(\mathbb{N})$ (the supermeum of a set in $\mathbb{R}$ is either in it, or is a limit point of it).

But of course, if that is not the case $\alpha$ is a limit point of $a(\mathbb{N})$. ie for each $\epsilon > 0$, there exists an infinite subsequence $a_{x_{1}}, a_{x_{2}}, \dots$ contained completely in the punctured ball $(\alpha -\epsilon, \alpha + \epsilon)\setminus\{\alpha\}$.

Therefore, we have $\alpha -\epsilon < a_{x_{i}} < \alpha$. but of course, since $a$ is non decreasing, for each $n > x_{1}$, we have $\alpha -\epsilon < a_{n} < \alpha$. thus, in either case our desired claim holds good.

Thus, let $a: \mathbb{N} \to \mathbb{R}$ be a weakly monotonic sequence. That is, either $a$ is (eventually) non decreasing and bounded above, or non increasing and bounded below, then, $a$ converges to either $\sup a(\mathbb{N})$ or, $\inf a(\mathbb{N})$ respectively.

Indeed, whenever $F: C \to D$ is a functor, between order categories, and $C_{\alpha}, \alpha \in \Gamma$ is a collection of objects in $C$ for which the supremum exists in $C$, and $F(C_{\alpha})$ is a collection of objects in $D$ for which the spremum exists in $D$,

we have

$$\sup_{\alpha \in \Gamma} F(C_{\alpha}) \le F(\sup_{\alpha \in \Gamma} C_{a})$$

This is true because $F$ transports the order into $D$, thus $F(\sup_{\alpha \in \Gamma} C_{\alpha})$ is an upper bound of each $F(C_{\alpha})$. And so the least upper bound of the collection $F(C_{\alpha})$ is at most any other upper bound.

Analogously, we have, whenever the infimum of the collections $C_{\alpha}$ and $F(C_{\alpha})$,

$$F( \inf_{\alpha \in \Gamma} C_{\alpha}) \le \inf_{\alpha \in \Gamma} F(C_{\alpha})$$

Approach from within:

Let $E_{1}, E_{2}, \dots \subset{ F }$ be a collection of elementary sets, for which $\sup_{n \in \mathbb{N}} E_{n} = \bigcup_{n \in \mathbb{N}} E_{n} = E$ is also elementary.

We have the following inequality: (the left hand side because $v$ is a functor from the order on $E_{n}, \subset{ }$ to $\mathbb{R}^+, \le$, the right hand side follows from monotonicity of $v$)

$$\sup_{n\ \in \mathbb{N}} v(E_{n}) \le v(E) \le v(F)$$

Now further suppose that $F$ is $E$ disjoint union with measure zero elements under $v$. of course $v(E) = v(F)$. Further suppose that whenever (for any) $\epsilon < v(E)$, there is some $n \in \mathbb{N}$ for which $e < v(E_{n})$, then we have

$$\sup_{n \in \mathbb{N}}v(E_{n}) = v(E) = v(F)$$

approach from without:

let $E_{1}, E_{2}, \dots \supset F$ be a collection of elementary sets, for which $\inf_{n \in \mathbb{N}}E_{n } = \bigcap_{n\in \mathbb{N}}E_{n} = E$ Then we have

$$\inf_{n\in \mathbb{N}}v(E_{n}) \ge v(E) \ge v(F)$$

Now, suppose $E$ is $F$ disjoint union with some meausre zero elements, then of course $v(E) = v(F)$ further suppose that for any $\epsilon > v(E)$ there exists some $n \in \mathbb{N}$ for which $\epsilon > v(E_{n}) > v(E)$. Thus, we have

$$\inf_{n \in \mathbb{N}}v(E_{n}) = v(E) = v(F)$$

In particular, the above equalities hold when $\lim_{ n \to \infty } v(E_{n}) = v(E)$.

Now, we want to characterize the values that $v$, a measure of elementary sets take. Due to translation invarience and finite additivity, it is sufficent to look at boxes whose corner is at the origin.

we write such boxes as $B = [0,X]$ where $X \in \mathbb{R}_{\geq 0}^d$ (that is each co-ordinate is non negative), of course $[0,X]$ is just notation for $\prod_{j=1}^d \langle 0, X_{j} \rangle$

Now, let $Q^n \in \frac{1}{n}\mathbb{Z}^d$. we want to know the measure, $v([0,Q^n])$. Let $A^n = \prod_{j=1}^d \{0,1,\dots,nQ^n_{j}-1\}$, $|A^n| = \prod_{j=1}^d nQ^n_{j}$.

It is clear that upto disjoint union measure with zero elements,

$$\bigsqcup_{x \in A^n} x + \langle0,1/n\rangle^d \subset [0,Q^n]$$

Thus, due to finite additivity and the fact that the remaining elements are measure zero, as well as translational invarience, we have

$$v([0,Q^n]) = |A^n| v(\langle0,1/n\rangle^d) = \frac{|A^n|}{n^d} v([0,1]^d)$$

since this is true for any measure $v$ of elementary sets, it is true for our good old elementary measure $m$. but of course $m([0,1]^d) = 1$

thus, there is a fixed constant $c = v([0,1])^d$ such that $v([0,Q^n]) = c m([0,Q^n])$

now let $P^n \in \frac{1}{n}\mathbb{Z}_{\geq 0}^d$ such that each $P^n_{j}$ is the largest one at most $X_{j}$.

notice, where $C^n = \prod_{j=1}^d \{0,1/n,\dots,P^n_{j}-1/n\}$

$$m([0,P^n]) = \frac{|C^n|}{n^d} = \frac{1}{n^d} \# \left([0,X] \cap \frac{\mathbb{Z}^d}{n}\right)$$

Thus of course, since $[0,X]$ is a box, by definition of $m$, $\lim_{ n \to \infty }m([0,P^n]) = m([0,X])$. But of course, the sequence $m([0,P^n])$ is increasing, and bounded above.

Thus (monotone convergence theorem above) $\sup_{n \in \mathbb{N}} m([0,P^n]) = m([0,X])$.

Now, we shall approach $[0,X]$ without. Notice $m([0,X]) \le m([0,P^n + 1/n])$

Where $[0, P^n + 1/n] := \prod_{j=1}^d \langle 0, P^n_{j} + 1/n \rangle$.

There is a very nice thing about $m$, namely that his measure on boxes is the product of measure of the intervals, Thus, it is sufficent to show that for any $j$, $\lim_{ n \to \infty } m(\langle 0, P^n_{j} + 1/n\rangle) = m(\langle 0, X_{j}\rangle)$

but of course, this is true, as $\lim_{ n \to \infty } P^n_{j} = X_{j}$ and $m(\langle 0, P^n_{j} + {1/n}\rangle) = P^j_{n} + {1/n}$.

But of course again, due to monotone convergence, we have $\inf_{n\in \mathbb{N}}m[(0,P^n + \frac{1}{n})] = m([0,X])$.

Now, notice since for each $n \in \mathbb{N}$ we have

$$[0,P^n] \subset{ } [0,X] \subset [0,P^n + 1/n]$$

Thus, we have

$$\sup_{n \in \mathbb{N}}v([0,P^n]) \le v([0,X]) \le \inf_{n\in \mathbb{N}} v([0, P^n + 1/n])$$

dividing by $c$ everywhere, we get $m([0,X]) \le v([0,X])/c \le m([0,X])$. Thus, $m([0,X]) = c v([0,X])$

That is, whenever $v: \mathscr{E}(\mathbb{R}^d) \to \mathbb{R}^+$ is a measure of elementary sets, we have a constant $c \in \mathbb{R}^+$ $c = v([0,1]^d)$ such that $m(E) = cv(E)$ for any elementary set $E$.

in other words, the elementary measure $m$ determines all measures of elementary sets upto constant factor.

Indeed, the elementary measure $m$ plays nice with dimension in the following way, let $d_{1},d_{2} \ge 1$, and $E_{1} \subset \mathbb{R}^{d_{1}}, E_{2} \subset \mathbb{R}^{d_{2}}$ be elementary sets. We claim that $E_{1} \times E_{2} \subset \mathbb{R}^{d_{1} + d_{2}}$ is elementary and that $m_{d_{1}}(E_{1})m_{d_{2}}(E_{2}) = m_{d_{1} + d_{2}}(E_{1} \times E_{2})$.

This is quite clearly true, let $E_{1} = \bigcup_{i=1}^T B_{i}$ and $E_{2} = \bigcup_{j=1}^S C_{j}$, (each is a disjoint union of boxes)

Then, $E_{1}\times E_{2} = \bigcup_{(i,j) \in [T] \times [S]} (B_{i} \times C_{j})$ so $E_{1} \times E_{2}$ is elementary

$$m(E_{1} \times E_{2}) = \sum_{j=1}^S \sum_{i=1}^T m(B_{i} \times C_{j})$$

let $B_{i} = \prod_{k=1}^{d_{1}} I^i_{k}$ and $C_{j} = \prod_{k=1}^{d_{2}} J^j_{k}$

clearly $B_{i} \times C_{j} = \prod_{k=1}^{d_{1}+d_{2}} R^{ij}_{k}$ where $R^{ij}_{k} = I^i_{k}$ when $1 \le k \le d_{1}$ and $R^{ij}_{k} = J^j_{k-d_{1}}$ when $d_{1} + 1 \le k \le d_{1} + d_{2}$

Of course then,

$$m(E_{1} \times E_{2}) = \sum_{j=1}^S \sum_{i=1}^T \prod_{k=1}^{d_{1} + d_{2}} |R^{ij}_{k}|$$

rearranging we get

$$m(E_{1} \times E_{2}) = \sum_{j=1}^S \left(\prod_{k=1}^{d_{2}}|J^j_{k}|\right)\sum_{i=1}^T \prod_{k=1}^{d_{1}} |I^i_{k}|$$

of course,

$$m(E_{1} \times E_{2}) = \sum_{j=1}^S(|C_{j}|m(E_{1})) = m(E_{1}) \sum_{j=1}^S |C_{j}|$$

Thus, finally, we get $m(E_{1} \times E_{2}) = m(E_{1}) m(E_{2})$.

This is pretty good, but you know, elementary sets can’t even be triangles or any other set that should be reasonably measurable.

Thus, we define the Jordan measures: Let $E \subseteq \mathbb{R}^d$ be a bounded set.

we have the jordan outer measure

$$m_J^*(E) := \inf_{\substack{E \subseteq A \\ A \text{ is elementary}}} m(A)$$

and the jordan inner measure

$$m_{*,J}(E) := \sup_{\substack{A \subseteq E \\ A \text{ is elementary}}} m(A)$$

We say that $E$ is jordan measurable if its outer and inner measures agree.

We define $\mathscr{E}^{O}(E) := \{A \in \mathscr{E}(\mathbb{R}^d) : E \subseteq A\}$ and $\mathscr{E}^{I}(E) := \{A \in \mathscr{E}(\mathbb{R}^d) : A \subseteq E\}$ to be the outer and inner elementary sets of $E$ respectively.

Due to the nature of supremum and infimum in $\mathbb{R}^+$, (even for finite sets) we have, for any $\epsilon > 0$, there exists $A \in \mathscr{E}^{O}(E)$ and $B \in \mathscr{E}^{I}(E)$ such that $m(A) - m_J^*(E) \le \epsilon$ and $m_J^*(E) - m(B) \le \epsilon$.

Exercise 1.1.5 (Characterisation of Jordan measurability). Let $E \subseteq \mathbb{R}^d$ be bounded. Show that the following are equivalent:

$E$ is Jordan measurable.

For every $\varepsilon > 0$, there exist elementary sets $A \subseteq E \subseteq B$ such that

$$m(B \setminus A) \leq \varepsilon.$$

For every $\varepsilon > 0$, there exists an elementary set $B$ such that

$$m_J^*(B \mathbin{\triangle} E) \leq \varepsilon.$$

$1 \implies 2$ follows directly: for each $\epsilon > 0$, we have elementary sets $A,B$ such that $A \subseteq E \subseteq B$ and $m(B) - m_J^*(E) \leq \epsilon/2$ and $m_{*,J}(E) - m(A) \leq \epsilon/2$. Since $E$ is Jordan measurable, the outer and inner measures are equal, so $m(B \setminus A) \leq \epsilon$.

$2 \implies 1$. Let $A,B$ be elementary sets, $A \subseteq E \subseteq B$. Clearly, $m(A) \le m_{*,J}(E)$ and $m_J^*(E) \le m(B)$. Therefore,

$$m(B\setminus A) \ge m_J^*(E) - m_{*,J}(E)$$

But since this is true for any such $A,B$, for each $\epsilon > 0$, there exists $A \subseteq E \subseteq B$ for which

$$\epsilon \ge m(B\setminus A) \ge m_J^*(E) - m_{*,J}(E)$$

Thus, $m_J^*(E) = m_{*,J}(E)$, ie $E$ is Jordan measurable. note: will need boxes with shaded interor and so on

$2 \implies 3$. let $\epsilon > 0$ and let $A,B$ be elementary sets, $A \subseteq E \subseteq B$ for which $m(B\setminus A) \le \epsilon$. Notice $B\setminus A \supseteq B \triangle E = B\setminus E$. Thus, $\epsilon \ge m(B\setminus A) \ge m_J^*(B \triangle E)$.

$3 \implies 2$: let $\epsilon > 0$, and let $B$ be an elementary set for which $m_J^*(B\triangle E) \le \epsilon/2$. Again due to the nature of the infimum, there exists an elementary set $A \supseteq B \triangle E$ such that $m(A) - m_J^*(B \triangle E) \le \epsilon/2$. Ie, $m(A) \le \epsilon$.

Now notice, since $B,A$ are elementary sets, $B\setminus A$ is an elementary set, and we further claim $B\setminus A \subseteq E$.

let $x \in B$ with $x \notin A$. Since $A \supseteq B\triangle E$, we have $x \notin (B\setminus E)$ and $x \notin (E\setminus B)$. Thus we have $x \in B \cap E$ thus $x \in E$.

Now notice that $A \cup B$ is an elementary set, and $A \cup B \supseteq E$ ($B \cup (B \triangle E) = B \cup E$, hence $A \cup B \supseteq (B\triangle E) \cup B \supseteq E$).

now notice since $(A\cup B)\setminus(B\setminus A) = A$, we have

$$m((A \cup B)\setminus(B\setminus A)) \le \epsilon$$

where $B\setminus A \subseteq E \subseteq A \cup B$.

Indeed, when $E$ is an elementary set, he is jordan measurable, and his jordan measure is equal to the elementary measure. thus we just use $m$ for both jordan measure and elementary measure.

Exercise 1.1.6. Let $E,F\subseteq\mathbb{R}^d$ be Jordan measurable sets.

(Boolean closure) Show that $E\cup F$, $E\cap F$, $E\setminus F$, and $E\triangle F$ are Jordan measurable.

(Non-negativity) Show that

$$m(E)\geq 0.$$

(Finite additivity) If $E,F$ are disjoint, show that

$$m(E\cup F)=m(E)+m(F).$$

(Monotonicity) If $E\subseteq F$, show that

$$m(E)\leq m(F).$$

(Finite subadditivity) Show that

$$m(E\cup F)\leq m(E)+m(F).$$

(Translation invariance) For any $x\in\mathbb{R}^d$, show that $E+x$ is Jordan measurable and

$$m(E+x)=m(E).$$

We will take them one by one.

Let $\epsilon > 0$, and $A \subseteq E \subseteq B$, $C \subseteq F \subseteq D$ (where $A,B,C,D$ are elementary sets) such that

$$m(B\setminus A), m(D\setminus C) \le \epsilon/2$$

(as shown above this is equivalent to saying E,F are jordan measurable)

Now note that $(B \cup D) \setminus (A \cup C) \subseteq (B\setminus A) \cup (D\setminus C)$.

Thus, due to the finite subadditivity of the elementary measure, we have $m((B \cup D) \setminus (A \cup C)) \le \epsilon$, where $A \cup C \subseteq E \cup F \subseteq B \cup D$. Thus $E \cup F$ is Jordan measurable.

Similarly, $(B \cap D) \setminus (A \cap C) \subseteq (B\setminus A) \cup (D\setminus C)$. That is, $m((B\cap D)\setminus(A\cap C)) \le \epsilon$ where $A \cap C \subseteq E \cap F \subseteq B \cap D$. Thus $E \cap F$ is Jordan measurable.

For difference, we will take the largest bit out of $A$ (namely $D$) and the smallest bit out of $B$ namely $C$.

Notice $A \setminus D \subseteq E \setminus F \subseteq B\setminus C$.

Also notice $(B\setminus C)\setminus(A\setminus D) \subseteq (B\setminus A) \cup (D\setminus C)$. thus,

$$m((B\setminus C)\setminus(A\setminus D)) \le \epsilon$$

. Therefore $E \setminus F$ is Jordan measurable, and since difference and finite union of Jordan measurable sets are Jordan measurable, we have $E \triangle F$ is Jordan measurable.

of course, the jordan measure of a jordan measuable set is non negative.

Now finite additivity, where $E,F$ are disjoint.

For ease, bring back the outer and inner elementary set notation.

First, notice

$$\{A \cup B : A \in \mathscr{E}^{I}(E),\ B \in \mathscr{E}^{I}(F)\} \subseteq \mathscr{E}^{I}(E \cup F)$$

(indeed, there maybe some non elementary sets $A \subset E$, $B \subset F$ where $A \cup B$ just magically happens to be elementary, so equality doesn’t need to hold) and

$$\{A \cup B : A \in \mathscr{E}^{O}(E),\ B \in \mathscr{E}^{O}(F)\} \subseteq \mathscr{E}^{O}(E \cup F)$$

Now, if $A \subset B$, in the reals, then supremum of $A$ is at most that of $B$ and infimum of $A$ is at least that of $B$.

Thus, taking the supremum in the first inclusion,

$$\begin{aligned} m(E\cup F) &= \sup_{C\in\mathscr{E}^{I}(E\cup F)}m(C) \\ &\geq \sup_{\substack{A\in\mathscr{E}^{I}(E) \\ B\in\mathscr{E}^{I}(F)}} m(A\cup B) \\ &= \sup_{\substack{A\in\mathscr{E}^{I}(E) \\ B\in\mathscr{E}^{I}(F)}} \bigl(m(A)+m(B)\bigr) \\ &= m(E)+m(F). \end{aligned}$$

On the other hand, taking the infimum in the second inclusion,

$$\begin{aligned} m(E\cup F) &= \inf_{C\in\mathscr{E}^{O}(E\cup F)}m(C) \\ &\leq \inf_{\substack{A\in\mathscr{E}^{O}(E) \\ B\in\mathscr{E}^{O}(F)}} m(A\cup B) \\ &\leq \inf_{\substack{A\in\mathscr{E}^{O}(E) \\ B\in\mathscr{E}^{O}(F)}} \bigl(m(A)+m(B)\bigr) \\ &= m(E)+m(F). \end{aligned}$$

Thus

$$m(E\cup F)=m(E)+m(F).$$

Monotonicity is quite obvious. Use inner elementary sets

Notice that $\mathscr{E}^{I}(E) \subseteq \mathscr{E}^{I}(F)$, thus taking supremum on the measure on both sides, we get $m(E) \le m(F)$.

As with elementary sets, its straightforward to prove finite subadditivity from here (we will leave it as a quick exercise for the reader) So is translational invarience.

Now, we recall that if $X,Y$ are metric spaces, then $f: X \to Y$ is continous, if for each $\epsilon > 0$ and for each $x \in X$ there exists some $\delta = \delta(x,\epsilon)$, such that, for each $x' \in B^X_{\delta}(x)$ we have $f(x') \in B^Y_{\epsilon}(f(x))$ equivalently, since $x' \in B^X_{\delta}(x)$ implies $f(x') \in f(B_{\delta}(x))$, the continuity condition can be written as $f(B_{\delta}(x)) \subset B_{\epsilon}(f(x))$.

The emphasis is that for a given output error $\epsilon$ and an input $x$, the input error $\delta$ around $x$ for which $f(x)$ is within $\epsilon$ is allowed to depend on both the input $x$ and the desired output error $\epsilon$.

Now, suppose $X$ is a compact metric space.

let $\epsilon > 0$. Now for each $x \in X$, let $\delta_{x} > 0$ be the real number for which $f(B_{\delta_{x}}(x)) \subset B_{\epsilon/2}(f(x))$.

of course the collection $\mathscr{B} = {B_{\delta_{x}}(x) : x \in X}$ is an open cover of $X$. Since $X$ is compact, using the lebegue number theorem (see algebra-5), we can manufacture $\lambda>0$ with respect to this cover $\mathscr{B}$ such that whenever $U \subset X$ and $\operatorname{diam}(U) < \lambda$ we have for some $B \in \mathscr{B}$, $U \subset B$. now for each $x \in X$, consider the ball $B_{\lambda/3}(x)$. Clearly the diameter of this ball is smaller than $\lambda$. Ie there exists some $B_{\delta_{x'}}(x') \in \mathscr{B}$ for which $B_{\lambda/3}(x) \subset B_{\delta_{x'}}(x')$. Thus, $f(B_{\lambda/3}(x)) \subset B_{\epsilon/2}(f(x'))$

Thus, notice by triangle inquality, that for any $y \in f(B_{\lambda/3}(x))$ we have $d_{Y}(y,f(x)) < \epsilon$ (since both of these points are in the $\epsilon/2$ ball around some $f(x')$).

Ie, $f(B_{\lambda/3}(x)) \subset B_{\epsilon}(f(x))$.

That is to say, for each $\epsilon > 0$, there exists a global $\delta = \delta(\epsilon)$ such that for each $x \in X$, $f(B_{\delta}(x)) \subset B_{\epsilon}(f(x))$.

Such continuity is called uniform continuity. Further, if needed $\delta$ is linear in $\epsilon$, ie there exists a global $L > 0$ for which $\delta = \epsilon/L$ we call the function $f$ Lipschitz continous.

The above discussion gives us the theorem: let $f: X \to Y$ be a continous map between metric spaces, where $X$ is compact, then $f$ is uniformly continous.

I apologize for using B to denote both balls and boxes, hopefully the context above makes it clear.

firstly, as seen in (analysis-0) we may replace open balls with open boxes freely in arguments of continuity when we are dealing with $\mathbb{R}^d$. Before we proceed, we make a lemma, since in general it becomes extremely unwieldy to give a covering of boxes by evenly sized ones, but we will need it over and over.

For any point $x \in \mathbb{R}^d$ and any $\epsilon > 0$, we define the right open box of size $\epsilon$ around $x$ as

$$I_\epsilon^*(x) := \prod_{j=1}^d [x_j-\epsilon,x_j+\epsilon).$$

and the open box of size $\epsilon$ around $x$ as

$$I_{\epsilon}(x):=\prod_{j=1}^d(x_j-\epsilon,x_j+\epsilon).$$

Box-cover lemma

Let $B = \prod_{j=1}^d [a_j,b_j] \subset \mathbb{R}^d$. For each $0 < t \leq \min_j(b_j-a_j)$, there exists a finite grid $P_t \subset B$ such that

$$C_t := \bigcup_{p \in P_t} I_t^*(p)$$

covers $B$ by pairwise disjoint boxes. Moreover,

$$m(C_t) = (2t)^d \prod_{j=1}^d \left\lfloor \frac{b_j-a_j+t}{2t}\right\rfloor$$

and

$$m(C_t) \leq \prod_{j=1}^d(b_j-a_j+t) \leq 2^d m(B).$$

proof: let $P_{j} = {a_{j} + t, a_{j} + 3t, \dots , a_{j} + (2r+ 1)t}$ where $r = \lfloor \frac{b_{j}-a_{j}-t}{2t} \rfloor$ clearly, $P_{j} \subset [a_{j},b_{j}]$, as $(2r + 1)t \le b_{j} - a_{j}$. Note $\#(P_{j}) = r+1 = \lfloor \frac{b_{j}-a_{j}+t}{2t} \rfloor$

On the other hand, $[a_{j},b_{j}]$ is covered (disjointly) by

$$\bigcup_{x \in P_{j}} [x-t,x+t)$$

Thus, we have $P_{t} = \prod_{j=1}^d P_{j}$. where whenever $p \neq q \in P_{t}$ $I_t^*(p) \cap I_t^*(q) = \emptyset$.

Thus, define $C_{t} = \bigcup_{p \in P_{t}} I_t^*(p)$, due to finite additivity, and traslational invarience of the elemntary measure, we have

$$m(C_t) = \#(P_{t})m([-t,t]^d)$$

Thus, we get the desired result.

This discussion helps with the following exercise:

Let $B$ be a closed box in $\mathbb{R}^d$, and $f: B \to \mathbb{R}$ be continous. Show that the graph $G_{f} = \{(x,f(x)) : x \in B\} \subseteq \mathbb{R}^{d+1}$ is Jordan measurable with Jordan measure $0$.

Terry Tao gives us a hint, since (by Heinie Borel) $B$ is compact, $f$ is uniformly continous, and thus we perhaps need to use this fact.

We will first give an upperbound of the outer measure of $G_{f}$.

let $\epsilon > 0$. Then there exists $\delta(\epsilon) > 0$ such that for each $x \in B$, we have $f(I_{\delta}(x)) \subset I_{\epsilon}(f(x))$.

Now, choose $t = min(\delta/2, min_{j}(b_{j}-a_{j}))$ (where $\pi_{j}(B) = [a_{j},B_{j}])$, thus we can safely say: by the box cover lemma, there exists a grid $P_{t} \subset B$ such that $C_{t} = \bigcup_{p \in P_{t}}I^*_{t}(p)$ covers $B$.

Hence $R_{t} = \bigcup_{p \in P_{t}}(I_t^*(p) \times f(I_t^*(p)))$ covers the graph $G_f$.

Now notice that since $I_t^*(p) \subset I_\delta(p)$, we have $f(I_t^*(p)) \subset I_\epsilon(f(p))$.

Thus,

$$S_{t} = \bigcup_{p \in P_{t}} I_t^*(p) \times I_\epsilon(f(p))$$

covers $G_{f}$ Now notice that $S_{t}$ is elementary in $\mathbb{R}^{d+1}$ Thus, due to finite subadditivity and the property that $m(A \times B) = m(A)m(B)$

we have

$$m(S_{t}) \le 2\epsilon \sum_{p \in P_{t}}m(I_t^*(p)) = 2\epsilon m(C_t)$$

thus we have using the upper bound in the box covering lemma

$$m(S_{t}) \le 2^{d+1}\epsilon (m(B))$$

Thus, given that $S_{t}$ covers $G_{f}$, for each $\epsilon > 0$ we have

$m_J^*(G_{f}) \le 2^{d+1}\epsilon m(B)$. That is, since the upper bound can be made arbitrarily small, we have $m_J^*(G_{f}) = 0$.

Since the inner measure is non negative, we have $0\le m_{*,J}(G_{f})\le m_J^*(G_{f}) = 0$. Thus, $m_{*,J}(G_{f}) = 0$.

Area under the graph: In the same setting, show that $A_{f} := \{(x,t) : x\in B,\ 0 \le t \le f(x)\}$ is Jordan measurable.

As before, let $\epsilon > 0$, we have some $\delta$ for which $f(I_{\delta}(x)) \subset (f(x)-\epsilon, f(x) + \epsilon)$.

Again, choosing $t = min(\delta/2, min_{j}(b_{j}-a_{j}))$ where $B = \prod_{j=1}^d[a_{j},b_{j}]$, we can use the box cover lemma to get the finite grid $P_{t} \subset B$ for which

$C_{t} = \bigcup_{p \in P_{t}} I_t^*(p)$ covers $B$. let $J_t(p) = I_t^*(p) \cap B$.

and define

$$D_{t} = \bigcup_{p \in P_{t}} J_{t}(p) \times [0,f(p) + \epsilon]$$

now, $x \in J_{t}(p)$ implies $x \in I_{\delta}(p)$ thus $f(x) \in (f(p)-\epsilon, f(p) + \epsilon)$. Therefore clearly, $D_{t}$ covers $A_{f}$.

further notice that

$$D_{t}\setminus A_{f} = \bigcup_{p \in P_{t}}\left((J_{t}(p) \times [0,f(p)+\epsilon]) \setminus A_{f}\right)$$

And hence,

$$D_{t}\setminus A_{f} \subseteq \bigcup_{p \in P_{t}}J_{t}(p) \times [f(p)-\epsilon, f(p)+\epsilon]$$

Therefore, noticing that the right hand side is elementary, and applying finite additivity we get

$$m_J^*(D_{t}\setminus A_{f}) \le 2\epsilon \sum_{p \in P_{t}} m(J_{t}(p))$$

first, we notice that $D_{t}\setminus A_{f} = D_{t}\triangle A_{f}$ as $A_{f} \subseteq D_{t}$. Then we notice that $\sum_{p \in P_{t}} m(J_{t}(p)) = m(B)$ since each $J_{t}(p) = I^*_{t}(p) \cap B$ are disjoint and cover $B$.

Thus we obtain $m_J^*(D_{t} \triangle A_{f}) \le 2\epsilon m(B)$.

Indeed, since the choice of $\epsilon$ was arbitrary, for any $\upsilon > 0$, by choosing $\epsilon = \upsilon/(2m(B))$ we have an elementary set $D$ for which $m_J^*(D \triangle A_{f}) \le \upsilon$. Thus by the characterization of Jordan measure (3), we have $A_{f}$ is Jordan measurable.

note all these arugments must be cleaned up

Exercise 1.1.8. Let $A,B,C$ be three points in $\mathbb{R}^2$.

(1) Show that the solid triangle with vertices $A,B,C$ is Jordan measurable.

(2) Show that the Jordan measure of the solid triangle is equal to

$$\frac12 |(B-A)\wedge(C-A)|,$$

where

$$|(a,b)\wedge(c,d)|:=|ad-bc|.$$

well, extending the triangles to meet the $x$-axis gives us a nice proof strategy.

we must also in general be careful about triangles that are obtuse, even if their bottom side lies on the $x$ axis, it is not the case that there is a function describing them.

we will show that the right angled triangle with base on the x-axis is jordan measurable, with the intended jordan measure.

first, due to translational invarience, we may consider the following right triangle, where $b > 0$, $h > 0$

$A = (0,0), B = (b,0), C = (b,h)$

Indeed, this is given by $f: [0,b] \to \mathbb{R}$ $f(x) = \frac{h}{b}x$.

firstly it is clear that this function is continous, and by the above result, $A_{f}$ is jordan measurable.

Now, let $E$ be an elementary set that covers $A_{f}$ Then, $E$ is a disjoint union of boxes:

$E = \bigcup_{i=1}^T \langle p_{i-1},p_{i}\rangle \times \langle 0,u_{i} \rangle$ where (taking intersection with $[0,b]$ if needed) $p_{0} = 0, p_{T} = b$.

it is further clear that for each $i$, $u_{i} \ge \frac{h}{b}p_{i}$

ie $m(E) \ge \frac{h}{b} \sum_{i=1}^T (p_{i}^2 - p_{i}p_{i-1})$ applying AM-GM we get

$$m(E) \ge \frac{h}{2b} \sum_{i=1}^T (p^2_{i}-p^2_{i-1}) = \frac{hb}{2}$$

Since this is true for any outer elementary approximation of $A_{f}$ we have $m_J^*(A_{f}) \ge bh/2$.

Now Let

$$C_{n} = \bigcup_{i=1}^n [(i-1)\frac{b}{n}, i\frac{b}{n}) \times [0,\frac{ih}{n}]$$

. Clearly $C_{n}$ covers $A_{f}$

notice

$$m(C_{n}) \le \frac{bh}{2n^2}(n(n+1)) = \frac{bh}{2}(1 + \frac{1}{n})$$

ie $m_J^*(A_{f}) \le bh/2$

Thus the claim holds, similarly, we can prove that if $A = (0,0), B = (0,b), C = (0,h)$ then $m(\Delta(A,B,C)) = \frac{bh}{2}$.

so we have the jordan measure of right triangles.

Now consider an arbitrary triangle whose base is on the $x$-axis.

ie $A = (a,0), B = (b,0), C = (m,n)$

and wlog suppose $b > a$.

we have case1: $a \le m \le b$ In this case, we partition the set into two right triangles, taking co-ordinate $C_{\perp} = (m,0)$

Due to finite additivity of disjoint sets (the line in between has measure zero) we have that firstly, since $\Delta(A,C,C_{\perp})$ and $\Delta(C,C_{\perp},B)$ are jurdan measurable, so is their union, and thus due to finite additivity, and translation we have

$$m(\Delta(A,B,C)) = \frac{n}{2}\left((m-a) + (b-m)\right) = \frac{1}{2} n(b-a)$$

case2: $a < b \le m$ yet again, with straightforward geometry,

we have $\Delta(A,B,C) = \Delta(A,C_{\perp},C) \setminus \Delta(B,C_{\perp},C)$ as sets, and indeed, due to finite additivity and so on, the Jordan measure acts on $m(E\setminus F) = m(E) - m(F)$ when $F \subseteq E$.

thus

$$m(\Delta(A,B,C)) = \frac{1}{2}n(b-a)$$

now for an arbitrary triangle translate the lowest vertex to the origin

say $A = (0,0), B = (p,q), C = (r,s)$

Moreover, without loss of generality, we may assume $C$ is the highest point.

Extend the line $BC$ to meet the $x$-axis at $D$. Thus

$$m(\Delta(A,B,C)) = m(\Delta(A,C,D)) - m(\Delta(A,B,D))$$

notice $D = (\frac{ps-rq}{s-q},0)$

thus we have

$$m(A,C,D) = \frac{s}{2}\left(\frac{ps-rq}{s-q}\right)$$

and

thus we have

$$m(A,B,D) = \frac{q}{2}\left(\frac{ps-rq}{s-q} - p\right)$$ $$\frac{1}{2}|ps - qr|.$$

(the absolute value is just there to relax all the symmettry assumptions we’ve made)

Notice if $a$ is not at the origin, say $a = (m,n)$

$$\frac{1}{2} \left| \begin{vmatrix} B_1-A_1 & C_1-A_1\\ B_2-A_2 & C_2-A_2 \end{vmatrix} \right|.$$

Jesus fucking christ we will now do the whole linear map thingy

exercise 1.1.9 show that every compact convex polytope is in $\mathbb{R}^d$ is Jordan measurable.

Indeed, a closed convex polytope is the intersection of finitely many half-spaces of the form $\{x\cdot v \le c\}$ where $v\in \mathbb{R}^d$, $c \in \mathbb{R}$ and its the usual dot product.

That is, a half space is basically the region under the $d-1$ plane given by $x \cdot v = 0$.

A closed convex polytope is compact if it is also bounded.

Initially, I was crying for a very long time. trying to understand something deep about the geometry of such polytopes. Though that is very beautiful, we will reserve it for another day.

let $P = H_{1} \cap H_{2} \cap \dots H_{n}$ be a compact convex polytope, Where $H_{i} = \{x\cdot v_{i} \le c_{i}\}$.

since $P$ is bounded, there exists a closed box $B$ for which $P \subset B$

Now notice that $P = \bigcap_{i=1}^n H_{i} \cap B$.

Thus, it is enough to show that the region given by a half space within a box is Jordan measurable, upon which we may invoke the fact that the finite intersection of Jordan measurable sets are Jordan measurable.

Ie, we need to show, for any closed box $B$ and any half space $H = \{v\cdot x \le c\}$, that $H \cap B$ is Jordan measurable. Since we have translational invarience, it is enough to show it for boxes whose corner is at the origin, upon which we can translate it around.

Just to be clear, we are not just translating the box around, we are translating the whole region the box intersected with the half-space, so this is okay.

Ie for each $B = \prod_{j=1}^d[0,b_{j}]$ and each half plane $H$ we need to show that $H \cap B$ is jordan measurable.

Indeed, we will show that there exists a continous map $h: B' = \prod_{j=1}^{d-1}[0,b_{j}] \to [0,b_{d}]$ such that $H \cap B = \{(x,t) : x \in B',\ 0 \le t \le h(x)\}$, and invoke the previous result, that the area under the graph of continous function on a compact space is Jordan measurable.

firstly, since not all $v_{j} = 0$, we may permute the co-ordinates (Ie the domain of $h$ will use a different set of d-1 axes) such that $v_{d} \neq 0$ (we do this cause otherwise $h$ is not well defined. )

Thus, we have

$$f(x_{1},x_{2},\dots x_{d-1}) = \frac{C -\sum_{j=1}^{d-1} x_{j}v_{j}}{v_{d}}$$

where $f: \mathbb{R}^{d-1} \to \mathbb{R}$ is an affine map which is continous, thus $h := f|B' : B' \to \mathbb{R}$ is a restriction of a continous map to a compact space, which is thus continous.

wow! what a beauty.

+# K6-Odd-Holes

The problem asks:

Let $G = (V,E)$ we say $G$ has a hole of size $n$ if there exists $n$ vertices $v_{1},v_{2},\dots v_{n}$ such that the vertex induced subgraph (take the vertices and ALL POSSIBLE EDGES BETWEEN THEM) is EXACTLY equal to $C_{n}$ (the cycle on n-verticies)

Notice, if there even one crossing edge, then it is not a hole.

Does there exist $G = (V,E)$ a simple graph, which is $K_{6}$ free, And also free of Odd holes of size at least 5, for which any two coloring of edges has a monochromatic triangle?

Well, the first instinct is to hit the extremal graph.

on $n$ verticies, the Turan graph, with 5-parts (and nearly equal verticies) has maximal edges, and is $K_{6}$ free.

We claim that it is also free of odd holes of size at least 5.

well, let $v_{1},v_{2},\dots v_{2k+1}$ be an odd hole, of size at least 5 ie $k \ge 2$

Since a 2 partite graph is odd cycle free, we must have that any odd hole should occupy at least 3 parts.

if part $v_{1},v_{3}$ is different (notice we have at least {v1,v2,v3,v4,v6}) then you have a chord (crossing edge)

Thus in general, $P(v_{i}) = p(v_{i+2})$

ie, all odd vertices must be in the same part as $v_{1}$ ie

$v_{1},v_{3},v_{5},\dots v_{2k+1}$ are all in the same part but of course then the cycle can’t be completed. no edge from $v_{2k+1} \to v_{1}$.

WOW! amazing, time to publish a paper I mean surely every coloring of this graph with many edges will have a monochrome triangle NOPE

NOT SO FAST MY FRIEND (this was a quip I saw in some book somewhere)

Indeed, there is a coloring, consider the 5 parts $P_{1},P_{2},P_{3},P_{4},P_{5}$

color a “consecutive part” edge red. Ie, if $e = x,y$ where $x \in p_{i}$, $y \in p_{i+1 \% 5}$ then color him red.

color all other edges blue. A triangle chooses 3 parts. and a “THICCC” edge between them. suppose $P_{i}, P_{j}, P_{k}$. wlog let $i < j < k$.

there aren’t too many options here. our claim is at least one of j-i, k-j, k-i is equal to 1 and at least one of them is greater than 1. (mod 5)

p1 = vertex {P_{1}} @ 0,0 [] 
p2 = vertex {P_{2}} @ 4,0 []
p3 = vertex {P_{3}} @ 0,4 []
p4 = vertex {P_{4}} @ 4,4 []
p5 = vertex {P_{5}} @ 2,7 []
e1 = edge(p1,p2)  [teal,thick]
e2 = edge(p2,p3) [teal, thick]
e3 = edge (p3,p4) [teal, thick] 
e4 = edge (p4,p5) [teal, thick]
e5 = edge (p5,p1) [teal, thick]
e6 = edge (p1,p3) [red, thick] 
e7 = edge (p1,p4) [red, thick]
e8 = edge (p2,p4) [red, thick]
e9 = edge (p2,p5) [red, thick]
e10 = edge (p3,p5) [red, thick]

yeah so the extreme turan graph has A COLORING WITH NO MONOCHROMATIC TRIANGLE SADGE, well on the bright side this is a real problem now.

we will give special names to everything.

$G$ is $K_{6}$ free is straight forward.

$G$ is free of odd holes of size at least $5$ we will call tight holed.

$G$ is good if it is both $K_{6}$ free and tight holed. (WHY INNUENDO? WHY?)

if $G$ is of the nature that any 2-coloring has a monochromatic triangle, then we have $G$ is Triangular.

$G$ is GREAT if it is good and Triangular.

The question is do great graphs exist?

On Triangular graphs.

let $G$ be a graph, and $\chi(G) \in {2,3,4,5}$ we claim $G$ is not Triangular.

This is equivalent (beautifully) to saying that $R(3,3) = 6$.

That is, make the THICC part graph, on $G$, which $\chi(G)$ parts.

there are only crossing edges, we will consider colorings where all crossing edges between the same two parts have the same color. so obviously the THICC part graph, in the worst case looks like $K_{5}$ and thus since $K_{r}$ for $2 \le r \le 5$ has a coloring with no monochromatic triangle, we are done.

That is to say, $G$ is triangular implies $\chi(G) \ge 6$.

Now suppose $\chi(G) \ge 6$. Does this imply that $G$ is triangular? if you give the thicc part graph, (same color for edges crossing a pair of parts) then obviously you can’t do it.

But again, not all colorings are THICC PART colorings. in fact $\overline{C_{11}}$ (the complement) has $\chi(G) \ge 6$ but also not triangular.

p1  = vertex {P_{1}}  @ 0,5 [rose]
  p2  = vertex {P_{2}}  @ 2.70,4.21 [rose]
  p3  = vertex {P_{3}}  @ 4.55,2.08 [green]
  p4  = vertex {P_{4}}  @ 4.95,-0.71 [green]
  p5  = vertex {P_{5}}  @ 3.78,-3.27 [gold]
  p6  = vertex {P_{6}}  @ 1.41,-4.80 [gold]
  p7  = vertex {P_{7}}  @ -1.41,-4.80 [blue]
  p8  = vertex {P_{8}}  @ -3.78,-3.27 [blue]
  p9  = vertex {P_{9}}  @ -4.95,-0.71 [gray]
  p10 = vertex {P_{10}} @ -4.55,2.08 [gray]
  p11 = vertex {P_{11}} @ -2.70,4.21 [rose]

  // Cyclic distance 2: teal
  e1  = edge(p1,p3)   [teal,thick]
  e2  = edge(p2,p4)   [teal,thick]
  e3  = edge(p3,p5)   [teal,thick]
  e4  = edge(p4,p6)   [teal,thick]
  e5  = edge(p5,p7)   [teal,thick]
  e6  = edge(p6,p8)   [teal,thick]
  e7  = edge(p7,p9)   [teal,thick]
  e8  = edge(p8,p10)  [teal,thick]
  e9  = edge(p9,p11)  [teal,thick]
  e10 = edge(p10,p1)  [teal,thick]
  e11 = edge(p11,p2)  [teal,thick]

  // Cyclic distance 3: teal
  e12 = edge(p1,p4)   [teal,thick]
  e13 = edge(p2,p5)   [teal,thick]
  e14 = edge(p3,p6)   [teal,thick]
  e15 = edge(p4,p7)   [teal,thick]
  e16 = edge(p5,p8)   [teal,thick]
  e17 = edge(p6,p9)   [teal,thick]
  e18 = edge(p7,p10)  [teal,thick]
  e19 = edge(p8,p11)  [teal,thick]
  e20 = edge(p9,p1)   [teal,thick]
  e21 = edge(p10,p2)  [teal,thick]
  e22 = edge(p11,p3)  [teal,thick]

  // Cyclic distance 4: red
  e23 = edge(p1,p5)   [red,thick]
  e24 = edge(p2,p6)   [red,thick]
  e25 = edge(p3,p7)   [red,thick]
  e26 = edge(p4,p8)   [red,thick]
  e27 = edge(p5,p9)   [red,thick]
  e28 = edge(p6,p10)  [red,thick]
  e29 = edge(p7,p11)  [red,thick]
  e30 = edge(p8,p1)   [red,thick]
  e31 = edge(p9,p2)   [red,thick]
  e32 = edge(p10,p3)  [red,thick]
  e33 = edge(p11,p4)  [red,thick]

  // Cyclic distance 5: red
  e34 = edge(p1,p6)   [red,thick]
  e35 = edge(p2,p7)   [red,thick]
  e36 = edge(p3,p8)   [red,thick]
  e37 = edge(p4,p9)   [red,thick]
  e38 = edge(p5,p10)  [red,thick]
  e39 = edge(p6,p11)  [red,thick]
  e40 = edge(p7,p1)   [red,thick]
  e41 = edge(p8,p2)   [red,thick]
  e42 = edge(p9,p3)   [red,thick]
  e43 = edge(p10,p4)  [red,thick]
  e44 = edge(p11,p5)  [red,thick]
 

OMG THAT IS SO PRETTY! also doesn’t have a monochromatic triangle.

He is good (tight-holed and k6 free) but not triangular. And he has $\chi(G) = 6$

A great graph, is thus necessarily, k6 free, tight holed, and is only $\ge 6$ colorable (vertex coloring).

But this is not sufficent.

we can run a computer program. (wow COMPUTER program)

We have another useful theorem.

definition, dual to the chromatic number, we have its clique number, $\omega(G)$ which is the size of the largest clique contained in $G$.

A graph is said to be perfect if, for every vertex-induced subgraph $H$ of $G$, we have $\chi(H)=\omega(H)$.

Strong perfect graph theorem:

$G$ is perfect if and only if it contains neither an odd hole, nor an odd anti-hole. (In this theorem all odd holes have size at least 5) IN GENERAL A HOLE IS DEFINED ONLY STARTING FROM SIZE 4, cause 3 is just a clique. some chordlessness of vertex induced subgraphs only makes sense from size 4 onwards.

where an anti-hole is is a complement of a hole. (In particular, contained an anti-hole means that the vertex induced subgraph is exactly the compliment of a cycle on those verticies)

Proof: (LEFT AS AN EXERCISE FOR FUTURE ME APPARANTLY ITS EXTREMELY NON TRIVIAL)

$G$ is GREAT implies

Suppose $G$ is GREAT. Then all of the following are necessary:

1. $G$ is $K_6$-free. Equivalently,

   $$\omega(G)\leq 5.$$

2. $G$ is tight-holed: it contains no vertex-induced cycle $C_{2k+1}$ for any $k\geq 2$.

3. $G$ is Triangular: every red-blue coloring of $E(G)$ contains a monochromatic triangle. In standard notation,

   $$G\longrightarrow (K_3,K_3).$$

4. $G$ is not $5$-colorable. Indeed, if $\chi(G)\leq 5$, take a proper vertex coloring of $G$, color the edges between each pair of vertex-color classes according to a triangle-free red-blue coloring of $K_5$, and obtain a red-blue coloring of $E(G)$ without a monochromatic triangle. Therefore

   $$\chi(G)\geq 6.$$

5. Consequently,

   $$\chi(G)>\omega(G),$$

   so $G$ is not perfect.

6. By the Strong Perfect Graph Theorem, a non-perfect graph contains an odd hole or an odd antihole. Tight-holed excludes the odd-hole outcome. Hence $G$ contains an induced odd antihole.

7. The antihole cannot be $\overline{C_5}$ because $\overline{C_5}=C_5$, which is an odd hole. It cannot have $13$ or more vertices because

   $$\omega\!\left(\overline{C_{2k+1}}\right)=k,$$

   so $\overline{C_{13}}$ and every larger odd antihole contain a $K_6$. Therefore every GREAT graph contains at least one of

   $$\boxed{\overline{C_7},\quad \overline{C_9},\quad \overline{C_{11}}}$$

   as a vertex-induced subgraph.

This last conclusion is the important computational reduction: we do not have to begin from arbitrary graphs. Every possible answer grows around at least one of these three compulsory cores.

Conditions imposed on the computation

We search by increasing number of vertices. For each of the three cores

$$A\in\left\{\overline{C_7},\overline{C_9},\overline{C_{11}}\right\},$$

we generate graphs containing a distinguished induced copy of $A$ and add vertices around it. A candidate survives only if it passes every filter below.

1. Simple-graph conditions

The adjacency matrix must be symmetric, have zero diagonal, and have entries in $\{0,1\}$. The distinguished vertices must induce exactly $A$; no edge of the core may be added or removed.

2. $K_6$-free filter

Reject the candidate as soon as six vertices are pairwise adjacent.

When attaching a single new vertex $v$ to the core, an immediate necessary condition is that $N(v)\cap A$ contain no $K_5$: otherwise that $K_5$ together with $v$ forms a $K_6$. This is only a quick local check; the full graph must still be checked for every possible $K_6$.

3. Tight-holed filter

Reject the candidate if any odd-sized vertex set of size at least $5$ induces exactly a cycle. It is not enough merely to detect an odd cycle: the cycle is forbidden only when it has no chord among its chosen vertices.

During incremental generation, test $A\cup\{v\}$ immediately after attaching a new vertex $v$. Later, also test odd holes involving several newly added vertices.

4. Chromatic filter

Reject the candidate if it admits a proper $5$-coloring. We do not require $\chi(G)=6$ exactly; values larger than $6$ remain legal. Computationally, the condition we need is simply

$$\chi(G)>5.$$

This filter is logically redundant once Triangularity has been proved, but it is a cheap and powerful rejection test before running the final edge-coloring check.

5. Triangularity as SAT

Give every edge $e\in E(G)$ a Boolean variable $x_e$. Interpret $x_e=1$ as red and $x_e=0$ as blue.

For every triangle with edges $e_1,e_2,e_3$, add the two clauses

$$(x_{e_1}\lor x_{e_2}\lor x_{e_3})$$

and

$$(\neg x_{e_1}\lor\neg x_{e_2}\lor\neg x_{e_3}).$$

The first clause forbids an all-blue triangle. The second forbids an all-red triangle.

• If the resulting SAT instance is satisfiable, the satisfying assignment is an explicit red-blue coloring with no monochromatic triangle. Reject $G$: it is not Triangular.
• If the instance is unsatisfiable, every red-blue edge-coloring has a monochromatic triangle. Thus $G$ is Triangular. If it has already passed the $K_6$ and tight-hole filters, then $G$ is GREAT.

Equivalently, form the triangle hypergraph $T(G)$ whose vertices are the edges of $G$ and whose hyperedges are the three-edge sets of the triangles of $G$. Then $G$ is Triangular exactly when $T(G)$ does not have Property B: its vertices cannot be $2$-colored without a monochromatic hyperedge.

6. Remove duplicate work

Graphs that differ only by relabeling are the same candidate. Use canonical labeling to keep one representative of each isomorphism class. While extending a fixed antihole core, quotient attachment patterns by the dihedral symmetries of that core.

This reduction affects speed only, not mathematical correctness.

7. Keep certificates

For every rejection or success, save something independently checkable:

• a set of six vertices for a discovered $K_6$;
• the ordered vertices and induced edge set of a discovered odd hole;
• a proper $5$-coloring;
• a red-blue edge-coloring witnessing that the graph is not Triangular;
• an UNSAT certificate when the Triangularity formula is unsatisfiable.

The first actual search is therefore:

Starting separately from $\overline{C_7}$, $\overline{C_9}$, and $\overline{C_{11}}$, add vertices through all legal attachment patterns, discard isomorphic duplicates, enforce $K_6$-freeness and tight-holedness at every step, discard $5$-colorable graphs, and ask SAT whether any surviving graph is Triangular.

A computational search extending $\overline{C_{11}}$ just works?

  v0  = vertex {v_{0}}  @ 0,7 []
  v1  = vertex {v_{1}}  @ 3.78,5.89 []
  v2  = vertex {v_{2}}  @ 6.37,2.91 []
  v3  = vertex {v_{3}}  @ 6.93,-1.00 []
  v4  = vertex {v_{4}}  @ 5.29,-4.58 []
  v5  = vertex {v_{5}}  @ 1.97,-6.72 []
  v6  = vertex {v_{6}}  @ -1.97,-6.72 []
  v7  = vertex {v_{7}}  @ -5.29,-4.58 []
  v8  = vertex {v_{8}}  @ -6.93,-1.00 []
  v9  = vertex {v_{9}}  @ -6.37,2.91 []
  v10 = vertex {v_{10}} @ -3.78,5.89 []
  z   = vertex {z}      @ 0,0 [gold]

  // Cyclic distance 2
  e1  = edge(v0,v2)   [teal]
  e2  = edge(v1,v3)   [teal]
  e3  = edge(v2,v4)   [teal]
  e4  = edge(v3,v5)   [teal]
  e5  = edge(v4,v6)   [teal]
  e6  = edge(v5,v7)   [teal]
  e7  = edge(v6,v8)   [teal]
  e8  = edge(v7,v9)   [teal]
  e9  = edge(v8,v10)  [teal]
  e10 = edge(v9,v0)   [teal]
  e11 = edge(v10,v1)  [teal]

  // Cyclic distance 3
  e12 = edge(v0,v3)   [teal]
  e13 = edge(v1,v4)   [teal]
  e14 = edge(v2,v5)   [teal]
  e15 = edge(v3,v6)   [teal]
  e16 = edge(v4,v7)   [teal]
  e17 = edge(v5,v8)   [teal]
  e18 = edge(v6,v9)   [teal]
  e19 = edge(v7,v10)  [teal]
  e20 = edge(v8,v0)   [teal]
  e21 = edge(v9,v1)   [teal]
  e22 = edge(v10,v2)  [teal]

  // Cyclic distance 4
  e23 = edge(v0,v4)   [teal]
  e24 = edge(v1,v5)   [teal]
  e25 = edge(v2,v6)   [teal]
  e26 = edge(v3,v7)   [teal]
  e27 = edge(v4,v8)   [teal]
  e28 = edge(v5,v9)   [teal]
  e29 = edge(v6,v10)  [teal]
  e30 = edge(v7,v0)   [teal]
  e31 = edge(v8,v1)   [teal]
  e32 = edge(v9,v2)   [teal]
  e33 = edge(v10,v3)  [teal]

  // Cyclic distance 5
  e34 = edge(v0,v5)   [teal]
  e35 = edge(v1,v6)   [teal]
  e36 = edge(v2,v7)   [teal]
  e37 = edge(v3,v8)   [teal]
  e38 = edge(v4,v9)   [teal]
  e39 = edge(v5,v10)  [teal]
  e40 = edge(v6,v0)   [teal]
  e41 = edge(v7,v1)   [teal]
  e42 = edge(v8,v2)   [teal]
  e43 = edge(v9,v3)   [teal]
  e44 = edge(v10,v4)  [teal]

  // The four new edges
  e45 = edge(z,v0)    [red,thick]
  e46 = edge(z,v2)    [red,thick]
  e47 = edge(z,v5)    [red,thick]
  e48 = edge(z,v8)    [red,thick]

we shall characterize $A_{n} = \overline{C}_{n}$ for $n \ge 4$ (A cause anti-hole)

let $K_{r}$ be a clique in $A_{n}$ this means that the verticies of $K_{r}$ is an independent set in $C_{n}$ Conversely a largest independent set $C_{n}$ is a largest clique in $A_{n}$

let $V = v_{0},v_{1}, \dots v_{n-1}$ be the verticies of $C_{n}$. let $A \sub V$ be an independent set.

to each $v_{i}$ in $A$, associate it with its suceeding vertex $v_{i+1}$ (indices are modulo $n$) since this map is injective. we have $|V| \ge 2|A|$ that is, $|A| \le \lfloor n/2 \rfloor$.

now let $A = v_{0}, v_{2}, \dots v_{2\cdot\lfloor n/2 \rfloor -2 }$

clearly $A$ is independent in $C_{n}$ (the neighbours of even index verticies are odd index verticies) and $|A|$ = $\lfloor n/2 \rfloor$.

That is, $\Omega(A_{n}) = \lfloor n/2 \rfloor$.

if $n \ge 6$, $A_{n}$ has no hole of length $5$ or greater.

suppose a vertex set $X$, $|X| = m$ induces $C_{m}$ in $A_{n}$, thus, $X$ induces $A_{m}$ in $C_{n}$ if $m \ge 6$, from the previous lemma, we have $A_{m}$ contains $K_{3}$. but whenenver $n \ge 6$ $C_{n}$ is triangle free. Thus a contradiction.

Therefore it must be that $m = 5$ but the compliment of $C_{5}$ is $C_{5}$. And clearly, when $n \ge 6$, no vertex induced subgraph of $C_{n}$ gives $C_{5}$.

We will now shift our focus to $A_{11}$. since $\Omega(A_{11}) = 5$, it is $K_{6}$ free. Further it has no odd holes. (it has no hole of length 5 or greater).

we will characterize triangle free colorings of $A_{11}$. Notice, $A_{11}$ is regular, with the degree of each vertex equal to $8$.

lemma: Any $2$-coloring of the edges of $A_{11}$ without a monochromatic triangle, has, for each vertex $v$, exactly $4$ red neighbours and $4$ blue neighbours.

(a red nieghbour of a vertex is a neighbour via a red edge)

Let the verticies of $A_{11}$ be labelled $v_{0},v_{1},\dots v_{10}$ in cyclic order. Suppose for contradiction that some vertex $v_{i}$ has (at least) $5$ blue neighbours in a 2-coloring of the edges of $A_{11}$ without a monochromatic triangle. Due to symmetry we may suppose $i = 0$ (otherwise re-label the vertices in cycling order starting at $v_{i}$)

let $v_{a_{0}}, v_{a_{1}}, .. v_{a_{4}}$ be blue neighbours of $v_{0}$

clearly, $2 \le a_{i} \le 9$, as $v_{1}, v_{10}$ are not neighbours of $v_{0}$

order them as $2 \le a_{0} < a_{1} < a_{2}< a_{3} < a_{4} \le 9$ it is clear that no matter how we choose $a_{i}$‘s, $a_{0}, a_{2}, a_{4}$ are non consecutive.

thus $v_{a_{0}}, v_{a_{2}}, v_{a_{4}}$ form a triangle, whose each edge is forced to be red. Which is a contradiction.

Therefore, every vertex has at most $4$ blue neighbours.

Similarly, every vertex has at most $4$ red neighbours.

Thus, every vertex of $A_{11}$ has exactly $4$ red and $4$ blue neighbours in a monochromatic triangle free coloring.

Indeed, $A_{11}$ contains $K_{5}$ induced by choosing any $5$ non consecutive verticies.

Any 2-coloring of the edges of $K_{5}$ that is triangle free has each color class (edge induced) equal to $C_{5}$.

This follows from noticing that at most $2$ neighbours of a vertex in $K_{5}$ can be red, and at most $2$ can be blue.

Ie, each vertex in $K_{5}$ has exactly $2$ red and $2$ blue neighbours.

Ie each induced color class is $2$-regular. There is only $1$ triangle free graph with $5$ verticies that is $2$-regular, namely $C_{5}$ (this is true by seeing that each edge leaves a vertex, and reaches another, so starting from $v_{1}$, you may hit $v_{2}$, and one more edge is needed, which hits $v_{3}$ and so on,using the handshaking lemma, we have to put $5$ edges, so eventually, some edge hits $v_{1}$ forming a cycle, notice that this cycle cannot have length $3$, and since we’re putting an odd number of edges, cannot have length $4$, thus has to have length $5$)

On $C_{n}$ with any cyclic labelling of verticies $v_{0},v_{1}, \dots v_{n-1}$ The cyclic distance $d(i,j) = \min{|j-i|, n - |j-i|}$ The shorter route.

Inherit the same labelling on $A_{n}$ and thus define cyclic distance on it.

Our claim is that: If a 2-coloring of the edges of $A_{11}$ is such that

1. $v_{0}v_{2}$ is colored red
2. The coloring has no monochromatic triangles.

Then, every edge $v_{i}v_{j}$ of cyclic distance $2$ or $3$ is colored red. while every edge of cyclic distance $4$, $5$ is colored blue.

Now let $G$ be an edge colored graph with edge coloring $\phi: E \to [c]$, and $v$ a vertex, for any $S$ subset of $adj(v)$ we define the color signature $\gamma(\phi,v,S): S \to [c]$ given by $\gamma(s) = \phi(vs)$

Overlap lemma: let $G = K_{4} \lor \overline{K_{2}}$. That is, $v_{0},v_{1},v_{2},v_{3}$ form $K_{4}$ and $v_{4}v_{5}$ is a non edge such that $v_{4}$ is adjacent to all $v_{0},..v_{3}$ and so is $v_{5}$.

Further let $G$‘s edges be two colored by $\phi$ such that there is no monochromatic triangle, and let $S ={v_{0},v_{1},v_{2},v_{3}}$ then $\gamma(v_{4},S) = \gamma(v_{5},S)$.

proof: Due to the previous lemma, and given that $K_{4} \vee v_{4}$ is $K_{5}$ and $K_{4} \vee v_{5}$ is $K_{5}$ (as vertex induced subgraphs)

Thus, they both have a red $C_{5}$ and a blue $C_{5}$ each. Deleting any one vertex, the leftover $K_{4}$ has a red $P_{4}$ and a blue $P_{4}$.

since the coloring is shared, $G-v_{4}$ and $G - v_{5}$ share the exact same red $P_{4}$ and blue $P_{4}$

for every $P_{4}$ the two unique endpoints needs to be joined by a vertex to get $C_{5}$.

In particular, take the red $P_{4}$, along with $v_{4}$ this forms a red $C_{5}$, and along with $v_{5}$ also forms a red $C_{5}$.

name the endpoints $r_{x}, r_{y}$ for the red $P_{4}$ and $b_{x},b_{y}$ for the blue $P_{4}$

we have have $c(r_{x}v_{4}) = c(r_{y}v_{4}) = c(r_{x} v_{5}) = c(r_{y}v_{5}) = r$ Similarly $c(b_{x}v_{4}) = c(b_{y}v_{4}) = c(b_{x} v_{5}) = c(b_{y}v_{5}) = b$

Now, we notice that ${r_{x}, r_{y}}$ and $b_{x}, b_{y}$ are disjoint sets. (not sure if this needs further proof)

and thus, their union is $v_{0},v_{1},.. v_{3}$.

Now, in $A_{11}$ define $Q_{i} = {i, i+2, i+4, i+6, i + 8}$ (indices are taken modulo 11, and $K_{5}(i)$ to be the maximal clique induced by these verticies.

Notice $Q_{i} \cap Q_{i+2}$ induces a $K_{4}$ with indicies ${i+2, i+4, i+6, i+8}$.

Moreover, since $v_{i+10} = v_{i-1}$, $v_{i}, v_{i+10}$ are non adjacent in $A_{11}$

Thus $Q_{i} \cup Q_{i+2}$ induces $K_{4} \vee \overline{K_{2}}$ (as an isomrohism of course)

Therefore we apply the overlap lemma, assuming that the underlying 2-coloring $\phi$ of $A_{11}$‘s edges is free of monochromatic triangles. thus, for each $k \in {2,4,6,8}$

(again all indicies are modulo 11) and any $i$,

we have $\phi(v_{i}v_{i+k}) = \phi(v_{i-1} v_{i+k})$

Now, let $Z_{11}$ be the cyclic group on the verticies of $A_{11}$.

we may denote every edge in $A_{11}$ by uniquely the pair $(i,k) \in X = Z_{11} \times {2,4,6,8}$ to mean the undirected edge $v_{i}v_{i+k}$ (the $Z_{11}$ cyclic group makes indexing concise, and $X$) is just a set, please note that ${2,4,6,8}$ is not a subgroup of $Z_{11}$ cause that bitch has prime order.

the map $T: X \to X$ can be inherited by the map on edges $v_{i}v_{i+k} \mapsto v_{i-1}v_{i+k}$ that the overlapping lemma preserves, along with the isomorphism (of sets) $v_{i-1}v_{i+k} \mapsto (i-1, k+1)$ but of course $k+1$ is odd, on the other hand, $v_{i+k}v_{i-1}$ is the same edge,

but notice $(i-1) - (i+k) = -k-1 = 10-k$ in $Z_{11}$

thus we send $v_{i-1}v_{i+k}$ to its canonical representative $(i+k,10-k)$

Thus, $T$ is the composition of isomorphisms, $(i,k) \mapsto (i+k, 10-k)$.

Now, since $T$ is a permutation on the set $X$, $1, T, T^2 ..$ is a cyclic group. What is the order of this group?

well notice that $T^2(i,k) = (i-1,k)$.

In this representation $(i,k)$ has cyclic distance $min(k, 11-k)$ (we mean the endpoints of the vertices of the edge represented by (i,k) has that cyclic distance) let $d: X \to [5]$ be the cyclic distance map. $X$ represents edges.

(I think it is better to leave out this esoteric $X$ and just directly work with edges, show that $(i,i+k) \to (i-1, i+k)$ where indicies are modulo 11? idk)

we have $d(T(x)) = d(x) + 1$ if $d(x)$ is even and $d(x)-1$ if $d(x)$ is odd. Moreover $d(T^2(x)) = d(x)$.

now let $x_{0} = (0,2)$ be a red edge. $d(x_{0}) = 2$. The orbit of $x_{0}$ under $T$ are the edges $x_{0}, Tx_{0}, T^2 x_{0}, \dots$ we are to show that these guys are each unique edges, and cover 22 edges.

thus all these edges are red, and have cyclic distance 2 or 3. On the other hand there are only 22 red edges, so the remaining 22 blue edges have cyclic distance 4 or 5.

WE KNOW THAT $T^{2k}$ is a subgroup of $T^n$, on the other hand $T^{2}$ sends $v_{i}v_{i+k} to$ I mean this is doable.

Thus we have the biggest theorem, every traingle free 2 coloring of the edges of $A_{11}$ is (upto swapping of colors) the one that colors all edges with cyclic distance 2 or 3 red, and 4 or 5 blue.

Consider a cyclic labling of vertices, $a_{0},\dots a_{10}$

Make a new graph $G$, $V(G) = V(A_{11}) \cup {z}$, $E(G) = E(A_{11}) \cup {za_{0},za_{2},za_{5},za_{8}}$

First notice that $V(A_{11})$ induces $A_{11}$ as a subgraph of $G$.

We claim that $G$ is $K_{6}$ free.

Well, $A_{11}$ is $K_{6}$ free.

Thus any $K_{6}$ must contain $z$ as a vertex, thus all verticies of this $K_{6}$ must be adjacent to $z$, ie $d(z) = 5$ contradicting the fact that $d(z) = 4$.

we claim that $G$ is odd hole free.

$A_{11}$ is free of holes of size $5$ or greater, thus, odd hole free. if $G$ has an odd hole, it must contain $z$.

let $C_{m}$ be a hole induced by selecting $z$ and $m-1$ verticies in $V(A_{11})$.

deleting $z$ leaves a vertex induced path on $m-1$ verticies in $A_{11}$. we claim that $m-1 \le 3$ and thus $m \le 4$.

well suppose $m-1 = 5$ then we have $P_{4} = v_{0},v_{1},v_{2},v_{3}$ as a vertex induced subgraph of $A_{11}$.

notice $\overline{P_{4}} = v_{0},v_{3},v_{1},v_{2}$ ie that one is in $C_{11}$ thus, the endpoints $v_{0},v_{3}$ are consecutive in $C_{11}$ thus $v_{0}v_{3}$ is a non edge in $A_{11}$.

so $m \le 4$ ie $G$ is odd hole free.

Now, for an arbitrary $2$-coloring of the edges of $G$, if the coloring on the subgraph $A_{11}$ has a monochromatic triangle we are done.

Otherwise $A_{11}$ has a special coloring.

In particular, $v_{0}v_{2}, v_{2}v_{5}, v_{5}v_{8}, v_{8}v_{0}$ is the same color, ie $C_{4} = v_{0} v_{2} v_{5} v_{8} v_{0}$ is monochromatic. (say red) On the other hand, $v_{0}v_{5}, v_{2} v_{8}$ are blue.

thus the $K_{4}$ induces by $v_{0}, v_{2}, v_{5}, v_{8}$ has $4$ red edges and $2$ blue edges.

Now the induced graph by taking $z, v_{0},v_{2},v_{5},v_{8}$ is $K_{5}$

If the inherited coloring is free of monochromatic triangles, it must have a red $C_{5}$ and a blue $C_{5}$ thus deleting $z$ should leave a red $P_{4}$ and blue $P_{4}$, which is impossible.