GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Combinatorics

Amelia Giles English 52 cards

Combinatorics

Cards in this deck (52)

  1. 1Ramsey Number definition.Ramsey Number definition.
  2. 2R(3,3) = 6 proof.R(3,3) = 6 proof.
  3. 3R(1,t) = 1 proof.R(1,t) = 1 proof.
  4. 4R(2,t) = t proof.R(2,t) = t proof.
  5. 5R(s,t) exists, then R(t,s) = R(s,t) proof.R(s,t) exists, then R(t,s) = R(s,t) proof.
  6. 6State Erdos and Szekeres theorem.State Erdos and Szekeres theorem.
  7. 7Erdos and Szekeres theorem: R(s,t) <= R(s-1,t) + R(s,t-1) proof.Erdos and Szekeres theorem: R(s,t) &lt;= R(s-1,t) + R(s,t-1) proof.
  8. 8R(s,t) <= (s+t-2 C s-1), R(t,t) <= (2t-1 C t-1) < 2^(2t-2) proof.R(s,t) &lt;= (s+t-2 C s-1), R(t,t) &lt;= (2t-1 C t-1) &lt; 2^(2t-2) proof.
  9. 9R(t) <- 2^(2t-1) proof.R(t) &lt;- 2^(2t-1) proof.
  10. 10Ramsey Number of s1,..,sk definition.Ramsey Number of s1,..,sk definition.
  11. 11Rk(s1,....,sk) exists proof.Rk(s1,....,sk) exists proof.
  12. 12R(3,4) = 9 proof.R(3,4) = 9 proof.
  13. 13State Erdos theorem.State Erdos theorem.
  14. 14Erdos: (n C t) * 2^(1 - (t C 2)) < 1 then R(t) > n proof.Erdos: (n C t) * 2^(1 - (t C 2)) &lt; 1 then R(t) &gt; n proof.
  15. 15t>= 4 then R(t) > floor( 2^(t/2) ) holds proof.t&gt;= 4 then R(t) &gt; floor( 2^(t/2) ) holds proof.
  16. 16State Ramsey number for sets.State Ramsey number for sets.
  17. 17R^(r)(s,t) <= R^(r-1)[R^(r)(s-1,t), R^(r)(s,t-1)] + 1 proof.R^(r)(s,t) &lt;= R^(r-1)[R^(r)(s-1,t), R^(r)(s,t-1)] + 1 proof.
  18. 18State Schur theorem.State Schur theorem.
  19. 19Schur theorem x+y=z proof.Schur theorem x+y=z proof.
  20. 20Any sequence of a1,...,an, n>st contains an increasing subsequence of length s+1 or a decreasing subsequence of t+1 proof.Any sequence of a1,...,an, n&gt;st contains an increasing subsequence of length s+1 or a decreasing subsequence of t+1 proof.
  21. 21Van der Waerden number definition.Van der Waerden number definition.
  22. 22Positional, strong, maker-breaker, breaker-maker game definition.Positional, strong, maker-breaker, breaker-maker game definition.
  23. 23Strategy definition.Strategy definition.
  24. 24Winning strategy for Breaker in maker-breaker game then S is a drawing strategy for P2 in the strong game proof.Winning strategy for Breaker in maker-breaker game then S is a drawing strategy for P2 in the strong game proof.
  25. 25Zermelo theorem.Zermelo theorem.
  26. 26There is no winning strategy for P2 in the strong game proof.There is no winning strategy for P2 in the strong game proof.
  27. 27If maker has a winning strategy in breaker-maker game then ...If maker has a winning strategy in breaker-maker game then ...
  28. 28Two statements that are true in a game.Two statements that are true in a game.
  29. 29Every red-blue-colouring of X yields a mono A in F. The P1 has a winning strategy for the strong game, moreover, maker has a winning strategy for the maker-breaker game proof.Every red-blue-colouring of X yields a mono A in F. The P1 has a winning strategy for the strong game, moreover, maker has a winning stra...
  30. 30Erdos-Selfridge theorem.Erdos-Selfridge theorem.
  31. 31Erdos-Selfridge theorem for breaker-maker game.Erdos-Selfridge theorem for breaker-maker game.
  32. 32Pairing strategy definition.Pairing strategy definition.
  33. 33The mxm n-in-a-row maker-breaker game...The mxm n-in-a-row maker-breaker game...
  34. 34Unrestricted-n-in-a-row maker-breaker game is a breakers win for every n>= 40 proof.Unrestricted-n-in-a-row maker-breaker game is a breakers win for every n&gt;= 40 proof.
  35. 35Maker and connectivity game theorem.Maker and connectivity game theorem.
  36. 36Maker wins connectivity game on multigraph G then G has two edge-disjoint spanning trees proof.Maker wins connectivity game on multigraph G then G has two edge-disjoint spanning trees proof.
  37. 37Lehman theorem.Lehman theorem.
  38. 38Lehman if multigraph G has two edge-disjoint spanning tress then maker wins the connectivity game on G proof.Lehman if multigraph G has two edge-disjoint spanning tress then maker wins the connectivity game on G proof.
  39. 39Poset definition.Poset definition.
  40. 40Poset maximal element definition.Poset maximal element definition.
  41. 41Chain and antichain definition.Chain and antichain definition.
  42. 42Mirsky theorem.Mirsky theorem.
  43. 43Mirsky theorem: largest chain in P has size r, then P can be partitioned into r antichains, proof.Mirsky theorem: largest chain in P has size r, then P can be partitioned into r antichains, proof.
  44. 44Dilworth theorem.Dilworth theorem.
  45. 45Hall theorem.Hall theorem.
  46. 46Hall: a bipartite graph with vertex classes A and B such that |N(S)|>=|S| for all S in A, contains a matching covering all of A, proof,Hall: a bipartite graph with vertex classes A and B such that |N(S)|&gt;=|S| for all S in A, contains a matching covering all of A, proof,
  47. 47Sperner’s lemma.Sperner’s lemma.
  48. 48YBLM inequality.YBLM inequality.
  49. 49YBLM inequality, proof.YBLM inequality, proof.
  50. 50Sperner’s lemma proof.Sperner’s lemma proof.
  51. 51Erdos theorem.Erdos theorem.
  52. 52Erdos theorem proof.Erdos theorem proof.

Information

Description
Flashcards on Combinatorics, created by Amelia Giles on 12/05/2023.
Created by
Amelia Giles
Views
1
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?