Skip to main content
added 13 characters in body
Source Link
Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.

The famous Nash-Williams conjecture claims that $\delta(G) \ge \frac{3}{4}n$ would be sufficient for $G$ to have a $K_3$-decomposition of its edges. (The constant is asymptotically sharp and Gustavsson's theorem answers in the affirmative with $\frac{3}{4}$ replaced by $1-10^{-24}$.)

To my untrained eye, this hypothesis on minimum degree has always seemed stronger than necessary. I am interested in weakening the hypotheses in the following direction.

If $\delta(G) > c n$ and $|E(G)|> \frac{3}{4}\binom{n}{2}$ then $G$ has a triangle decomposition.

(That is, if the minimum degree of $G$ is not too small while the average degree is at least what Nash-Williams demands, then we still have a $K_3$-decomposition.)

I can make silly counterexamples for $c \lesssim 3/28$. Just take a $K_3$-divisible but non-$K_3$-decomposable graph on $m$ vertices which is $\lesssim 3/4$-dense and disjoint union with a clique of order $6 m+1$. The resulting graph has $n=7m+1$ vertices, minimum degree about $3n/28$, and average density $\gtrsim (3/4+6^2)/7^2 = 3/4$.

Why would one want to make a hard conjecture even harder? I suppose it is just an attempt to understand what really makes it hard!

So here comes my MO question. Are there any obvious counterexamples to the above for $\frac{3}{28} < c < \frac{3}{4}$?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.

The famous Nash-Williams conjecture claims that $\delta(G) \ge \frac{3}{4}n$ would be sufficient for $G$ to have a $K_3$-decomposition. (The constant is asymptotically sharp and Gustavsson's theorem answers in the affirmative with $\frac{3}{4}$ replaced by $1-10^{-24}$.)

To my untrained eye, this hypothesis on minimum degree has always seemed stronger than necessary. I am interested in weakening the hypotheses in the following direction.

If $\delta(G) > c n$ and $|E(G)|> \frac{3}{4}\binom{n}{2}$ then $G$ has a triangle decomposition.

(That is, if the minimum degree of $G$ is not too small while the average degree is at least what Nash-Williams demands, then we still have a $K_3$-decomposition.)

I can make silly counterexamples for $c \lesssim 3/28$. Just take a $K_3$-divisible but non-$K_3$-decomposable graph on $m$ vertices which is $\lesssim 3/4$-dense and disjoint union with a clique of order $6 m+1$. The resulting graph has $n=7m+1$ vertices, minimum degree about $3n/28$, and average density $\gtrsim (3/4+6^2)/7^2 = 3/4$.

Why would one want to make a hard conjecture even harder? I suppose it is just an attempt to understand what really makes it hard!

So here comes my MO question. Are there any obvious counterexamples to the above for $\frac{3}{28} < c < \frac{3}{4}$?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.

The famous Nash-Williams conjecture claims that $\delta(G) \ge \frac{3}{4}n$ would be sufficient for $G$ to have a $K_3$-decomposition of its edges. (The constant is asymptotically sharp and Gustavsson's theorem answers in the affirmative with $\frac{3}{4}$ replaced by $1-10^{-24}$.)

To my untrained eye, this hypothesis on minimum degree has always seemed stronger than necessary. I am interested in weakening the hypotheses in the following direction.

If $\delta(G) > c n$ and $|E(G)|> \frac{3}{4}\binom{n}{2}$ then $G$ has a triangle decomposition.

(That is, if the minimum degree of $G$ is not too small while the average degree is at least what Nash-Williams demands, then we still have a $K_3$-decomposition.)

I can make silly counterexamples for $c \lesssim 3/28$. Just take a $K_3$-divisible but non-$K_3$-decomposable graph on $m$ vertices which is $\lesssim 3/4$-dense and disjoint union with a clique of order $6 m+1$. The resulting graph has $n=7m+1$ vertices, minimum degree about $3n/28$, and average density $\gtrsim (3/4+6^2)/7^2 = 3/4$.

Why would one want to make a hard conjecture even harder? I suppose it is just an attempt to understand what really makes it hard!

So here comes my MO question. Are there any obvious counterexamples to the above for $\frac{3}{28} < c < \frac{3}{4}$?

Source Link
Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17

Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.

The famous Nash-Williams conjecture claims that $\delta(G) \ge \frac{3}{4}n$ would be sufficient for $G$ to have a $K_3$-decomposition. (The constant is asymptotically sharp and Gustavsson's theorem answers in the affirmative with $\frac{3}{4}$ replaced by $1-10^{-24}$.)

To my untrained eye, this hypothesis on minimum degree has always seemed stronger than necessary. I am interested in weakening the hypotheses in the following direction.

If $\delta(G) > c n$ and $|E(G)|> \frac{3}{4}\binom{n}{2}$ then $G$ has a triangle decomposition.

(That is, if the minimum degree of $G$ is not too small while the average degree is at least what Nash-Williams demands, then we still have a $K_3$-decomposition.)

I can make silly counterexamples for $c \lesssim 3/28$. Just take a $K_3$-divisible but non-$K_3$-decomposable graph on $m$ vertices which is $\lesssim 3/4$-dense and disjoint union with a clique of order $6 m+1$. The resulting graph has $n=7m+1$ vertices, minimum degree about $3n/28$, and average density $\gtrsim (3/4+6^2)/7^2 = 3/4$.

Why would one want to make a hard conjecture even harder? I suppose it is just an attempt to understand what really makes it hard!

So here comes my MO question. Are there any obvious counterexamples to the above for $\frac{3}{28} < c < \frac{3}{4}$?