Timeline for Sum of squared degrees in tripartite graph
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2021 at 6:32 | comment | added | Seva | Your sum is $o(n^3)$, and you cannot do better than, say, $n^3e^{-c\sqrt{\ln n}}$; google for the "diamond-free lemma". | |
| Sep 25, 2021 at 21:26 | history | edited | Marcel K. Goh | CC BY-SA 4.0 |
added picture
|
| Sep 25, 2021 at 20:38 | comment | added | Marcel K. Goh | @Seva Yes, sorry that I am not being very clear. I do actually mean to say that no two triangles in the graph share an edge. Furthermore, one can assume that every edge is in a triangle. If you have an answer, I would be happy to accept it, since my question is too general to really be interesting but at least for this special case we could get a bound. | |
| Sep 25, 2021 at 20:34 | comment | added | Seva | It is not the same as no two triangles sharing an edge! | |
| Sep 25, 2021 at 20:30 | comment | added | Marcel K. Goh | @Seva Yes, the graph is a union of triangles that possibly share vertices but not edges. | |
| Sep 25, 2021 at 20:28 | comment | added | Seva | Do you mean that no two triangles in your graph share a common edge? If so, $O(n^2)$ is easy. | |
| Sep 25, 2021 at 19:57 | history | edited | Marcel K. Goh | CC BY-SA 4.0 |
reduction to cherries
|
| Sep 25, 2021 at 19:13 | comment | added | Marcel K. Goh | Okay, what went wrong was my statement that if the edge set of the graph is a union of disjoint triangles, then the number of cherries is the number of edges. This is wrong because the triangles may share vertices (but not edges). | |
| Sep 25, 2021 at 18:18 | comment | added | Marcel K. Goh | @Seva Thanks for this calculation! It is quite surprising to me that the sum of the squares is on the same order as the number of edges in my tripartite graph because it raises an apparent contradiction. I will work it out precisely to see what is going on. | |
| Sep 25, 2021 at 18:15 | comment | added | Seva | In this count, every triple $(u,v,w)$ gives raise to two cherries. (That is, the cherries are oriented.) If we let $M$ denote the number of nonoriented cherries, then the sum of the squares is $2M+2e$, which for a union of triangles gives $4e$ for the sum of the squares. | |
| Sep 25, 2021 at 18:01 | comment | added | Seva | The sum of squares is $N+2e$, where $N$ is the number of cherries and $e$ is the number of edges of the graph. Thus, if the graph is the union of edge-disjoint triangles, then the sum is precisely equal to $3e$. | |
| Sep 25, 2021 at 17:57 | comment | added | Marcel K. Goh | @Seva In the case where the edge set is a union of disjoint triangles, the number of cherries is exactly the number of edges. Does this mean that $d(G)$ is roughly the number of edges? | |
| Sep 25, 2021 at 17:42 | comment | added | Seva | The sum of squares of the degrees is, essentially, the number of "cherries" (triples of vertices $(u,v,w)$ with $v$ adjacent to both $u$ and $w$). The rest depends on exactly what do you want to prove. | |
| Sep 25, 2021 at 17:26 | history | asked | Marcel K. Goh | CC BY-SA 4.0 |