Last wins - DPChallenge Forums

02/04/2014 12:27:09 PM · #23577

Originally posted by bvy:

Originally posted by beatabg:

Originally posted by bvy:
I'll post the final proof tomorrow.

That's some real suspense. I can tell everyone is waiting. I know I am.

Finally, some enthusiasm. Okay, here we go:

For k >= 0, let P_k denote the family of all k-degenerate graphs, and for some graph G, let X_(P_k)(G) represent the minimum number of partitions of the vertices of V(G) necessary for each partition to induce a k-degenerate subgraph of G. A graph G is said to be l-critical with respect to X_(P_k) if X_(P_k)(G) = l but X_(P_k)(G - v) = l - 1 for every v in G.

If G is l-critical with respect to X_(P_k), then d(G) >= (k + 1)(l - 1).

Proof: Let u be a vertex of least degree in G. Since G is l-critical with respect to X_(P_k), we can partition the vertices of G as follows: Place u in a partition by itself, and partition the remaining vertices of G into (necessarily) l - 1 subsets. Each of these l partitions induces a k-degenerate subgraph, including the single vertex u which is k-degenerate for all k >= 0. Observe that u must be incident with some vertex in each of the l - 1 partitions, for otherwise it could be included in any other partition as a disconnected vertex, and the induced subgraph would still be k-degenerate. Hence, deg(u) >= (l - 1). Expanding on that, u must be incident with at least k + 1 vertices in any partition such that it requires a partition all its own, and deg(u) >= (k + 1)(l - 1). Hence, d(G) >= (k + 1)(l - 1).

This concludes my exploration of the properties of k-degenerate graphs. Thank you all for your support. I next plan to share some fundamental results about edge colorings. At this point, I'm studying Vizing's Theorem and working through an interesting proof that uses induction. (I don't plan to restate it here as it's rather long, though not terribly complicated.) More to come...

Spork says you should show that with a zero-knowledge proof.

Spork wins

02/04/2014 01:52:16 PM · #23578

Hey guess what.

I WIN!!!!!!

Pentax DA 18-135mm F3.5-5.6ED AL [IF] WR DC

02/04/2014 03:39:38 PM · #23579

Not really.

Spork wins.

tnun

Ricoh GR III

02/04/2014 03:59:43 PM · #23580

fast readers win.

f'rinstance, bvy's proof, if speed read, says fork u, u degenerates: Viszla's think better than you and besides are savvy about guinea pig (degu) colourings. like bon appetit, smart chops.

ha. qed.

Jules1x

Fujifilm X-T1

Fujifilm XF 23mm f/1.4 R

02/04/2014 04:00:49 PM · #23581

1+2+3+4+...to inifity = -1/12.

(Thanks Krulwich Wonders)

Do I have to post the full proof or do I win?

Message edited by author 2014-02-04 16:01:14.

02/04/2014 04:52:35 PM · #23582

Only zero knowledge proofs allowed, but you can't win either way.

Spork wins...the rest of you are here to celebrate and pay him tribute.

02/04/2014 05:15:17 PM · #23583

02/04/2014 05:54:16 PM · #23584

That's good just be quiet and sit in the corner while I win

02/04/2014 06:10:26 PM · #23585

Being quiet isn't my fortÃ©. Winning is.

02/04/2014 06:43:15 PM · #23586

Not so much.

Spork wins.

02/04/2014 06:48:46 PM · #23587

But for the occasional temporary interruption, I am always winning.

Canon EF 200mm f/2.8 L II USM Lens

02/04/2014 10:38:05 PM · #23588

except when you're not, which is all of the time.

Spork wins.

skewsme

Canon EOS-6D

02/04/2014 10:40:18 PM · #23589

what? no fortÃ© jokes? and you call yourselves immature?

the99

Sony DSLR-A100

Sony DT 18-70mm f/3.5-5.6 Aspherical ED Zoom Lens for Sony Alpha

02/05/2014 12:28:50 AM · #23590

nobody is immature here

Canon EF 200mm f/2.8 L II USM Lens

02/05/2014 02:03:00 AM · #23591

I know you are, but what am I? Winning. That's what. Nyeah.

bvy

Sigma DP1x

02/05/2014 07:46:17 AM · #23592

Originally posted by Art Roflmao:

I almost want a print. Almost.

skewsme

Canon EOS-6D

02/05/2014 10:30:00 AM · #23593

Originally posted by the99:

nobody is immature here

Speak for yourself, ya old forte.

02/05/2014 10:37:28 AM · #23594

Im the king of the world!!!!!!!!!!!!!

02/05/2014 11:10:47 AM · #23595

You may float like a butterfly, but you sting like a cottonball.

Spork wins

02/05/2014 11:50:56 AM · #23596

Off with his head

02/05/2014 12:47:37 PM · #23597

Cowboys don't eat cake...

Spork wins.

02/05/2014 05:01:48 PM · #23598

I love cookies......hhhhhmmmmmm