Probabilistic method and graph theory

Question

1. Let $G$ be a simple graph with maximum degree $9$ and $e$ edges. Show that we can partition the set of vertices into two sets such that the number of edges between two set is at least $\frac{5}{9}e$.

2. Show that there is a graph on $n$ vertices with at least $O(n^{4/3})$ edges and without any square.

Answer 1

Here's a solution to problem 2:

We construct a random graph on $n$ vertices by adding each edge with probability $p$, independently and uniformly. Thus, the expected number of edges is $p\binom{n}{2}$. For every collection $S$ of four vertices, we have that the probability they form a square is $p^4$. For every square that is formed, we remove one edge, thereby removing the square from the graph. Thus, the expected number of edges is greater than or equal to $$ p \binom{n}{2} - 3 p^4 \binom{n}{4}.$$ Taking $p = n^{-2/3}$ gives that this expectation is $O(n^{4/3})$, implying there is a graph with no squares having at least $O(n^{4/3})$ edges.

Answer 2

For path I.

Consider complete graph that has $|E(G)|=\frac{n(n-1)}{2}$ number of edges, an example about simple graphs. Show first that $K_n$ satisfy the condition and prove inductively on each spanning subgraph of $K_n$ such as $K_k -h$ where $h$ is an edge satisfy the condition. Your goal is to show that the condition is satisfied with every simple subgraph.

I haven't proved this but the below shows the idea. You may need to partition again after the removal to satisfy the condition again.

Example

Consider $K_{9}$ with vertex sets $S$ and $H$: you start with all vertices in $S$. Move one vertex to $H$ so nice edges between $S$ and $H$. Move second vertex to $H$ so $(9-1)+8=16$ vertex between $S$ and $H$. You can increase the number of edges between $S$ and $H$ until 4 vertices in $S$ and $5$ in $H$. So $9+8+7+6 \geq 4*5=20$ vertices between $S$ and $H$ is the maximum edge count. $4+3+2+1=10$ edges in $H$ and $3+2+1=6$ edges in $S$. And $|E(K_9)|=36 =20+10+6$. Notice that $5/9\cdot |E(G)|=5/9\cdot 36=20$ so the condition is satisfied.

Now remove an edge $h$ between the sets $S$ and $H$ so the graph $G-h$ has 35 edges so $5/9\cdot 35=19.4444....> 19$ so the condition is not satisfied. This means the graph $K_9-h$ must be partioned again until again 20 edges between $S$ and $H$. In next removal, $34\cdot 5/9>19$ so only 19 edges now required between $S$ and $H$.