Dominik Farhan

Notes for the talk on Turán number of C1,3C_{1,3}


Here you can find my notes to my presentation on the paper Note on the Turán number of the 3-linear hypergraph C1,3C_{1,3} by the authors: Chaoliang Tang, Hehui Wu, Shengtong Zhang, Zeyu Zheng.

I presented this paper in a talk for the Spring School of Combinatorics 2023.

Here is the handout for the talk.

Regarding the notation

The authors of the paper use C13C_{13} to denote the discussed graoh. I decided to denote it as C1,3C_{1,3}. I assume that the comma was dropped because of brevity. As we will see in a second including comma in C1,3C_{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.

The notes follow.


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 33-linear hypergraph C13C_{13}. This talk is going to have 44 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 nn for the number of vertices and ss for the number of vertices with a degree at least 66.

Previous work

So what do we already know about the ex(n,C1,3)ex(n, C_{1,3})? Two years ago, Gyárfás, Ruszinkó and Sárkozy proved the following 6n34+ϵex(n,C1,3)2n6 \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 00 whenever n30,1mod4n-3 \equiv 0, 1 \mod 4, it is 11 whenever n32mod4n-3 \equiv 2 \mod 4 and 33 otherwise.

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

Here we will show a stronger result which is E(G)3(ns)2.|E(G)| \leq \frac{3(n - s)}{2}. We are also going to prove that whenever there is some small number of huge vertices (s2s \leq 2) the bound can be made even tighter E(G)10(ns)7.|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)3(ns)2|E(G)| \leq \frac{3(n - s)}{2}. To do that we need to introduce two new symbols. First the symbol capital DD. D({x,y,z})a,b,cD(\{x, y, z\}) \geq \langle a, b, c \rangle to say that d(x)ad(x) \geq a, d(y)bd(y)\geq b and d(z)cd(z) \geq c for positive integers a,b,ca,b,c where abca \geq b \geq c. We will use this later.

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

Plan of the attack

  1. Proof by contradiction. Minimal counter-example.
  2. Observation using χ(v)d(v)\frac{\chi(v)}{d(v)}
  3. From the observation, by the pigeonhole principle we will see the existence of some special edge
  4. Analysis of d(v)d(v)s' of the edge
  5. Only possible case satisfies assumption in the lemma. We can use the lemma. Lemma will create a contradiction with the minimality of the counter example.

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

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

The core of this proof is the observation that we can express nsn-s as a sum of the following fractions. Recall that ss is the number of vertices of degree six or more. eEve,vVχ(v)d(v)=vVve,eEχ(v)d(v)=ns.\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)d(v) edges. So the second sum is the fraction χ(v)d(v)\frac{\chi(v)}{d(v)} added degree of vv times. When d(v)6d(v)\geq 6, χ(v)=0\chi(v)=0 so we get nsn-s.

Now, from our initial assumption, we get that 23E(G)>ns\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 χ(x)d(x)+χ(y)d(y)+χ(z)d(z)\frac{\chi(x)}{d(x)} + \frac{\chi(y)}{d(y)} + \frac{\chi(z)}{d(z)} for some edge {x,y,z}\{x, y, z\}.

Because the sum of sums is equal to nsn-s which is less than the number of edges times 23\frac{2}{3}, at least one of these inner sums is less than 23\frac{2}{3} (pigeon hole principle). χ(x)d(x)+χ(y)d(y)+χ(z)d(z)<23.\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)d(y)d(z)d(x) \leq d(y) \leq d(z). What we can say about the degree of xx. Surely it cannot be one because then the inequality wouldn't hold. So it's at least 22. By similar reasoning d(y)>4d(y) > 4. 22 or 33 is not possible because d(x)d(y)d(x) \leq d(y) and then the assumption would not hold. Again the same reasoning gives that d(z)5d(z)\geq 5. Now if d(z)6d(z) \geq 6 then we have C1,3C_{1,3}. Why? We just pick an edge e1e_1 adjacent to xx. Then because d(y)4d(y)\geq 4 we can pick e2e_2 containing yy that doesn't share a vertex with e1e_1 and similarly we pick e3e_3. So we will assume that d(z)=5d(z) = 5. Now the inequality implies that D(e)5,5,4D(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 ESE_S are subsets of SS. This tells us that the graph induced by vertices in SS is a component of GG. Let's look at what happens when we remove SS from GG. GSG - S. What is the number of vertices? It's n=n11n' = n - 11. What is the number of vertices with of degree at least 66? It's the same! s=ss' = s. And the number of edges? E(GS)=E(G)13>3(ns)213=3n3s262>3n333s2|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 GG. 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 GG be the minimal crown-free graph with s2s\leq 2 and E(G)>10(ns)7|E(G)|> \frac{10(n - s)}{7}.

We again define χ\chi but this time differently. χ(v,e)=1\chi(v, e) = 1 for d(v)<6,d(v)3d(v) < 6, d(v)\neq3, χ(v,e)=0\chi(v,e)=0 for d(v)6d(v)\geq 6 and for d(v)=3d(v)=3 suddenly ee is also important χ(v,e)=1.05\chi(v,e) = 1.05 if there is a vertex in ee with degree at least 66. Otherwise let χ(v,e)=0.9\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. eEve,vVχ(v,e)d(v)=vVve,eEχ(v,e)d(v)ns.\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 s2s\leq 2).

We assumed that E(G)>10(ns)7|E(G)|> \frac{10(n - s)}{7}. Again by the pigeonhole principle we have that there is an edge e={x,y,z}e=\{x, y, z\} such that χ(x,e)d(x)+χ(y,e)d(y)+χ(z,e)d(z)<710.\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)2d(x)\geq 2. Now d(y)3d(y)\leq 3 is not possible, no matter the degree of zz. Thus d(y)4d(y)\geq 4. And the rest is pretty much the same as in the previous proof so we won't do it.

Any questions? :)

Now I would like to attempt the proof of the lemma.

But first, let me give you some definitions. I'm going to use e={x,y,z}e = \{x,y,z\} for the edge from the lemma that satisfies D(e)5,5,4D(e)\geq \langle 5,5,4\rangle. I'm also going to use G(p)G(p), where p{x,y,z}p\in\{x,y,z\} for the set of all vertices that lie on the same edge as pp and not containing any of vertices of ee (basically a neighborhood).

Plan of the attack

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

Without loss of generality, d(y),d(z)5d(y), d(z) \geq 5 and d(x)4d(x)\geq 4. We already discussed that we cannot have D(e)6,4,2D(e)\geq \langle 6, 4, 2 \rangle so it is not possible for any of the vertices y,zy, z to have a degree six or more. Therefore d(y)=d(z)=5d(y) = d(z)= 5.

I claim that G(z)=G(y)G(z) = G(y) and that G(x)G(y)G(x)\subset G(y).

Let's start with the first claim. Let's say it is false and G(y)G(y) contains vertex vv not in G(z)G(z). From the definition of GG, there is an edge e1e_1 different from ee that contains vv. Then at most one edge adjacent to zz different from ee contains a vertex in e1e_1 (the remaining vertex). So we have three edges containing z and disjoint from e1e_1. We can now take any edge-disjoint from e1e_1 that contains xx, let's call it e2e_2. Then from those three edges that are disjoint from e1e_1 at least one is disjoint from e2e_2, this edge together with ee, e1e_1, and e2e_2 form the crown. Therefore G(z)=G(y)G(z) = G(y).

Now to the second claim. Again suppose the contrary and let there be an edge e1e_1 adjacent to xx containing vertex not in G(y)G(y). Then among all the edges containing zz there is surely some not intersecting e1e_1. Let's call this edge e3e_3. From the four edges adjacent to yy and different from ee, at most two can intersect e3e_3 and at most one can intersect e1e_1. Take the one disjoint from the rest and you have the crown. So we proved G(x)G(y)G(x)\subset G(y).

Now we have S{x,y,z}=G(y)=G(z)G(x)S\setminus \{x,y,z\} = G(y) = G(z) \supset G(x). We are nearly there. Let FF be the set of all edges in the graph GG that contain one of the vertices in SS, but are disjoint from {x,y,z}\{x,y,z\}. If we show that it is empty, we are essentially finished.

Remember, the lemma tells us that G[S]G[S] is a connected component. We can prove that by showing that FF is empty.

We will define an auxiliary bipartite graph as follows H=(ZH,YH,EH)H = (Z_H, Y_H, E_H) s.t. ZH={eizei}Z_H = \{e_i \mid z \in e_i \}, Yh={ejyej}Y_h = \{e_j \mid y \in e_j \}, EH={{ei,ej}eiej}E_H = \{ \{e_i, e_j\}\mid e_i \cap e_j \neq \emptyset \}. Edges will be vertices. We are going to take edges intersecting zz to ZHZ_H and edges intersecting yy to YHY_H.

What do we know about this bipartite graph? Surely there are 88 vertices. 44 in YY part, 44 in ZZ part. Another observation is that each vertex is of degree exactly 22. Ok, so we have a 22-regular bipartite graph on 88 vertices. There are only two possible configurations we can have. Either we have a cycle of length 88 or two squares. Because this bipartite graph is going to help us with the proof it would be quite nice to know if we are dealing with two squares or C8C_8.

I claim that it cannot be C8C_8. And proof of this is very elegant.

Now, let's take some edge intersecting xx that has the other two vertices in G(x)G(x). Because G(x)G(y)G(x) \subset G(y) this edge can intersect with at most 44 vertices of the bipartite graph. 22 in YHY_H and 22 in ZHZ_H. Let's call these vertices WW. We can now delete these vertices from the graph. If there are any two vertices in HWH-W that don't share an edge we can take them and construct the crown from them {x,y,z}\{x,y,z\} and the edge with xx. So we are not allowed to have two vertices from different parts that do not share an edge. Because HWH-W has at least 44 vertices, it contains a K2,2K_{2,2}. Therefore we are dealing with two squares.

Now, we would like to show that FF is empty and I will just show the general idea. Remember that FF is the set of all edges that contain vertex in SS but are disjoint from {x,y,z}\{x, y, z\}. We will assume the contrary and take fFf \in F. Now, we will show that no matter what vertices are in small ff we can always create the contradiction.

Before we do that we need to do one last thing and that is to show that all edges containing xx other than {x,y,z}\{x,y,z\} are surely from the the following set {{x,a,d},{x,b,c},{x,r,q},{x,s,p}.}\{ \{x,a,d\}, \{x,b,c\}, \{x,r,q\}, \{x,s,p\}. \} This will make the later analysis of possible cases easier. How can we do that? First, let's assume that there is an edge containing xx with one vertex in {a,b,c,d}\{a,b,c,d\} and the other in {r,s,p,q}\{r,s,p,q\}. By symmetry let this edge be {x,a,r}\{x, a, r\} . Then we have crown as {z,a,b},{y,b,d},{z,p,q},{x,a,r}\{z,a,b\}, \{y,b,d\}, \{z,p,q\}, \{x,a,r\}.

Now, from the linearity, it is not possible to have edges {x,?,?}\{x, ?, ?\} where both ?? are in one edge of YHY_H or ZHZ_H. What we are left are just those two edges.

From now on we need to use the symmetry of the problem and the fact that we know all possible edges containing xx. Armed with this, we can show that no matter how we choose elements of small ff we get a contradiction. That way there can be no such ff which essentially completes the proof of the lemma.

With this I'd like to end and thank you for your attention. If you have any questions you can ask them now or talk to me later during the week. Thank you.