Regarding the notation

The authors of the paper use $C_{13}$ to denote the discussed graoh. I decided to denote it as $C_{1,3}$. I assume that the comma was dropped because of brevity. As we will see in a second including comma in $C_{1,3}$ feels more natural given the structure of the corresponding hypergraph.

The whole paper deals with hypergraphs but I am going to refer to them simply as graphs for brevity.

Lastly, the proof of the lemma is slightly confusing in the original paper so I changed the notation little bit to make it easier to digest. Nonetheless, the proof otherwise corresponds to the one in the paper.

Intro

I'd like to welcome you to my talk. If you should have any questions during the talk, do not hesitate to ask.

I am going to talk about the paper by: Chaoliang Tang, Hehui Wu, Shengtong Zhang, Zeyu Zheng.

The paper, I'd like to discuss is called Note on the Turán number of the $3$-linear hypergraph $C_{13}$. This talk is going to have $4$ parts. First, we will look at some definitions so we are all familiar with the needed notation. Then I'll show you some of the previous work and introduce what the quartet discovered. Then we will prove it using one non-trivial lemma. Till the end, I will attempt to prove that lemma which will be rather juicy.

Let's start with definitions.

I will also use $n$ for the number of vertices and $s$ for the number of vertices with a degree at least $6$.

Previous work

So what do we already know about the $ex(n, C_{1,3})$? Two years ago, Gyárfás, Ruszinkó and Sárkozy proved the following $$6 \left\lfloor \frac{n - 3}{4} \right\rfloor + \epsilon\leq ex(n, C_{1,3}) \leq 2n$$ where $\epsilon$ changes based on the nominator. It is $0$ whenever $n-3 \equiv 0, 1 \mod 4$, it is $1$ whenever $n-3 \equiv 2 \mod 4$ and $3$ otherwise.

This was recently improved by Fletcher who showed that $ex(n, C_{1,3})< \frac{3}{5}n$.

Here we will show a stronger result which is $$|E(G)| \leq \frac{3(n - s)}{2}.$$ We are also going to prove that whenever there is some small number of huge vertices ($s \leq 2$) the bound can be made even tighter $$|E(G)| \leq \frac{10(n-s)}{7}.$$

So how can we prove all of this?

Proving the first theorem

Let's start with the first theorem and prove $|E(G)| \leq \frac{3(n - s)}{2}$. To do that we need to introduce two new symbols. First the symbol capital $D$. $D(\{x, y, z\}) \geq \langle a, b, c \rangle$ to say that $d(x) \geq a$, $d(y)\geq b$ and $d(z) \geq c$ for positive integers $a,b,c$ where $a \geq b \geq c$. We will use this later.

Then we need $\chi(v)$. Which will be a function taking vertex and giving us $1$ or zero based on the degree $d(v)$.

Now, we are ready to do the proof. Suppose the contrary. That there is a crown-free graph with more than $\frac{3(n-s)}{2}$ edges. Let $G$ be the smallest of all these crown-free graphs having more than $\frac{3(n-s)}{2}$ edges.

First, let's specify the $\chi(v)$. This function essentialy indicates whether $v$ is a large vertex or a small one. It can have only two values $\chi(v) = 1$ whenever $d(v) \leq 5$, $\chi(v) = 0$ otherwise.

The core of this proof is the observation that we can express $n-s$ as a sum of the following fractions. Recall that $s$ is the number of vertices of degree six or more. $$\sum_{e\in E} \sum_{v\in e, v \in V} \frac{\chi(v)}{d(v)} = \sum_{v\in V} \sum_{v\in e, e \in E} \frac{\chi(v)}{d(v)} = n - s.$$ Why should this be true? The first equality is just swapping sums. That's simple. The second: each vertex is contained in $d(v)$ edges. So the second sum is the fraction $\frac{\chi(v)}{d(v)}$ added degree of $v$ times. When $d(v)\geq 6$, $\chi(v)=0$ so we get $n-s$.

Now, from our initial assumption, we get that $\frac{2}{3}|E(G)| >n-s$. Now when we look at the first sum, we have a number of edges inner sums of the form $$\frac{\chi(x)}{d(x)} + \frac{\chi(y)}{d(y)} + \frac{\chi(z)}{d(z)}$$ for some edge $\{x, y, z\}$.

Because the sum of sums is equal to $n-s$ which is less than the number of edges times $\frac{2}{3}$, at least one of these inner sums is less than $\frac{2}{3}$ (pigeon hole principle). $$\frac{\chi(x)}{d(x)} + \frac{\chi(y)}{d(y)} + \frac{\chi(z)}{d(z)} < \frac{2}{3}.$$

Now, without the loss of generality assume that degrees are non-decreasing $d(x) \leq d(y) \leq d(z)$. What we can say about the degree of $x$. Surely it cannot be one because then the inequality wouldn't hold. So it's at least $2$. By similar reasoning $d(y) > 4$. $2$ or $3$ is not possible because $d(x) \leq d(y)$ and then the assumption would not hold. Again the same reasoning gives that $d(z)\geq 5$. Now if $d(z) \geq 6$ then we have $C_{1,3}$. Why? We just pick an edge $e_1$ adjacent to $x$. Then because $d(y)\geq 4$ we can pick $e_2$ containing $y$ that doesn't share a vertex with $e_1$ and similarly we pick $e_3$. So we will assume that $d(z) = 5$. Now the inequality implies that $D(e) \geq \langle5, 5, 4 \rangle$.

Now we will need to use the lemma I mentioned earlier.

This lemma sounds complicated. But in fact, the one important thing it tells us is in the last sentence and that is that all elements of $E_S$ are subsets of $S$. This tells us that the graph induced by vertices in $S$ is a component of $G$. Let's look at what happens when we remove $S$ from $G$. $G - S$. What is the number of vertices? It's $n' = n - 11$. What is the number of vertices with of degree at least $6$? It's the same! $s' = s$. And the number of edges? $|E(G - S)| = |E(G)| - 13 > \frac{3(n-s)}{2} - 13 = \frac{3n - 3s' - 26}{2} > \frac{3n - 33 - 3s'}{2}$. Which contradicts the minimality of $G$. Hence we are finished!

Now when we proved the first theorem, we will quickly prove the second.

Proof of the second theorem

The proof is similar to the first one. The only real difference is in the $\chi$ function which now takes also edges into account.

So again, suppose the contrary. Let $G$ be the minimal crown-free graph with $s\leq 2$ and $|E(G)|> \frac{10(n - s)}{7}$.

We again define $\chi$ but this time differently. $\chi(v, e) = 1$ for $d(v) < 6, d(v)\neq3$, $\chi(v,e)=0$ for $d(v)\geq 6$ and for $d(v)=3$ suddenly $e$ is also important $\chi(v,e) = 1.05$ if there is a vertex in $e$ with degree at least $6$. Otherwise let $\chi(v,e)= 0.9$ (it is interesting to think where the previous weighting function fails).

From this, we get a similar formula involving sums as in the previous case. $$\sum_{e\in E} \sum_{v\in e, v \in V} \frac{\chi(v, e)}{d(v)} = \sum_{v\in V} \sum_{v\in e, e \in E} \frac{\chi(v,e)}{d(v)} \leq n - s.$$ Why is it not equal? (answer $s\leq 2$).

We assumed that $|E(G)|> \frac{10(n - s)}{7}$. Again by the pigeonhole principle we have that there is an edge $e=\{x, y, z\}$ such that $$\frac{\chi(x,e)}{d(x)} + \frac{\chi(y,e)}{d(y)} + \frac{\chi(z,e)}{d(z)} < \frac{7}{10}.$$

We again do a few observations on the degrees of vertices of the edge. Without loss of generality let degrees be non-decreasing. Surely $d(x)\geq 2$. Now $d(y)\leq 3$ is not possible, no matter the degree of $z$. Thus $d(y)\geq 4$. And the rest is pretty much the same as in the previous proof so we won't do it.

Any questions? :)

Plan of the attack

1. WLOG $d(y), d(z)\geq 5$ and $d(x)\geq 4$.
2. From this we will show that $d(y) = d(z) = 5$.
3. Show that $S \setminus \{x,y,z\} = G(y) = G(z) \supset G(x)$
4. Define $F$ to be the set of all edges containing vertex from $S$ but disjoint from $e$
5. Start the proof that $F = \emptyset$
6. Create an auxiliary bipartite graph $H$, where vertices are some edges of $G$.
7. Show that $H$ looks like $2$ squares
8. Assume that some $f\in F$. Show that no matter what vertices are in $f$ we get a contradiction. Use the symmetry of $H$ to only consider a few cases.