Talk:Triangle-free graph

re: triangle-finding problem

I changed the bound for the $A^{3}$ algorithm to $O(n^{3})$ instead of $O(n^{2.376})$. 2.376 is the best-known exponent right now, yes, (see here), but it hasn't been implemented anywhere (this is mentioned on the link), and using $n^{2.376}$ instead of the classical and recognizable $n^{3}$ is confusing or misleading to anyone who doesn't follow recent developments in numerical linear algebra. Charibdis (talk) 01:12, 22 December 2010 (UTC)

I undid your changes since the article makes no sense after them. In particular, the n³ matrix multiplication algorithm is slower than the m^1.41 time bound of the other algorithm, even for dense matrices, so it is nonsensical to say that the matrix algorithm (without the fast matrix multiplication techniques) is an improvement on the other algorithm. —David Eppstein (talk) 02:48, 22 December 2010 (UTC)

Independent set of size √n

We need a reference for "An independent set of √n vertices in an n-vertex triangle-free graph is easy to find." This would imply that the 5-cycle is 3-colorable. Should it perhaps be the floor of √n ? — Preceding unsigned comment added by Gruberan (talk • contribs) 21:29, 24 November 2012 (UTC)

I think that except for K₂ and C₅ it's the ceiling, not the floor. The reasoning is that, if its maximum degree is Δ, then either $\Delta \geq {\sqrt {n}}$ in which case we find a large independent set as the neighborhood of one vertex, or $\Delta \leq {\sqrt {n}}$ in which case by Brooks' theorem there exists a Δ-coloring and one of the color classes is large enough. The exceptional cases for Brooks' theorem are the odd cycles and complete graphs, but the only ones of those that cause any problem are K₂ and C₅. I agree that a source for this reasoning would be appropriate. —David Eppstein (talk) 22:00, 24 November 2012 (UTC)

Dense Triangle Hypothesis easily provable?

​

For each n in {3,4,5,6,...}, consider the n-vertex graphs

(justbipart) the complete bipartite graph such that [the parts have floor(n/2) and ceil(n/2) vertices] and [the floor(n/2),ceil(n/2) vertex parts consist of the low,high index vertices respectively]

and

(bipartplus) that graph plus 1 or more additional edges

.

The justbipart graphs are triangle-free, since they are bipartite. The low,high index parts of the justbipart graphs have at least 1,2 vertices respectively, so for each such n there is at least one bipartplus graph, and all such graphs have a triangle. (Use the ends of an additional edge and a vertex in the other part.)

Thus, triangle detection is at least as hard as distinguishing the justbipart graphs from the bipartplus graphs. For the adjacency matrix, they all agree on entries where the two vertices are equal (bit is 0) and on entries with one low-index vertex and one high-index vertex (bit is 1), which leaves the entries where the indices are not equal but are both low or both high. For justbipart graphs, these entries are all 0. Each other symmetric (about the main diagonal) choice of bits for those entries gives an adjacency matrix of a bipartplus graph, so dense triangle detection is at least as hard as computing the OR of x bits, where x is the number of such entries on each side of the main diagonal.

x = ((number of low indices) choose 2) + ((number of high indices) choose 2) = (floor(n/2) choose 2) + (ceil(n/2) choose 2) >= (floor(n/2) choose 2) + (floor(n/2) choose 2) = 2*(floor(n/2) choose 2) = 2*floor(n/2)*(floor(n/2)-1)/2 = floor(n/2)*(floor(n/2)-1) >= ((n-1)/2)*(((n-1)/2)-1) = ((n/2)-(1/2))*(((n/2)-(1/2))-1) = ((n/2)-(1/2))*((n/2)-(3/2)) = ((1-o(1))*(n/2)*((1-o(1))*(n/2) = ((1-o(1))*((1-o(1))*(n/2)*(n/2) = ((1-o(1))*((n^2)/4) = (1/(1+o(1)))*((n^2)/4) = (1*(n^2))/((1+o(1))*4) = (n^2)/(4+o(1))

, so triangle detection for dense n-vertex graphs is at least as hard as computing the OR of (n^2)/(4+o(1)) bits.

Computing the OR of (n^2)/(4+o(1)) bits requires Theta(n^2) queries, so in particular triangle detection for dense n-vertex graphs requires Omega(n^2) time.

If this doesn't prove the "dense triangle hypothesis", then the article should clarify what that hypothesis is.

JumpDiscont (talk) 23:17, 31 July 2024 (UTC)

There was a typo in the statement of the dense triangle hypothesis. It should be the hypothesis that no time bound of the form $O(n^{\omega -\delta })$ is possible, where $\omega$ is the exponent of fast matrix multiplication. —David Eppstein (talk) 00:43, 1 August 2024 (UTC)