DBpedia – Linked Data Fragments

Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Hales–Jewett_theorem> ?p ?o }

• Hales–Jewett_theorem abstract "In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be \"completely random\".An informal geometric statement of the theorem is that for any positive integers n and c there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, or certain diagonal (more details below) of length n all of whose cells are the same color. In other words, the higher-dimensional, multi-player, n-in-a-row generalization of game of tic-tac-toe cannot end in a draw, no matter how large n is, no matter how many people c are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension H. By a standard strategy stealing argument, one can thus conclude that if two players alternate, then the first player has a winning strategy when H is sufficiently large, though no practical algorithm for obtaining this strategy is known.More formally, let WnH be the set of words of length H over an alphabet with n letters; that is, the set of sequences of {1, 2, ..., n} of length H. This set forms the hypercube that is the subject of the theorem. A variable word w(x) over WnH still has length H but includes the special element x in place of at least one of the letters. The words w(1), w(2), ..., w(n) obtained by replacing all instances of the special element x with 1, 2, ..., n, form a combinatorial line in the space WnH; combinatorial lines correspond to rows, columns, and (some of the) diagonals of the hypercube. The Hales–Jewett theorem then states that for given positive integers n and c, there exists a positive integer H, depending on n and c, such that for any partition of WnH into c parts, there is at least one part that contains an entire combinatorial line.For example, take n = 3, H = 2, and c = 2. The hypercube WnH in this caseis just the standard tic-tac-toe board, with nine positions:A typical combinatorialline would be the word 2x, which corresponds to the line 21, 22, 23; another combinatorial line is xx, which is the line11, 22, 33. (Note that the line 13, 22, 31, while a valid line for the game tic-tac-toe, is not considered a combinatorial line.) In this particular case, the Hales–Jewett theorem does not apply; it is possible to dividethe tic-tac-toe board into two sets, e.g. {11, 22, 23, 31} and {12, 13, 21, 32, 33}, neither of which containa combinatorial line (and would correspond to a draw in the game of tic-tac-toe). On the other hand, if we increaseH to, say, 8 (so that the board is now eight-dimensional, with 38 = 6561 positions), and partition this boardinto two sets (the \"noughts\" and \"crosses\"), then one of the two sets must contain a combinatorial line (i.e. no draw is possible in this variant of tic-tac-toe). For a proof, see below.".
• Hales–Jewett_theorem wikiPageExternalLink Mathematics_by_collaboration.
• Hales–Jewett_theorem wikiPageExternalLink blogging-tic-tac-toe-and-the-future-of-math.
• Hales–Jewett_theorem wikiPageID "640714".
• Hales–Jewett_theorem wikiPageLength "12379".
• Hales–Jewett_theorem wikiPageOutDegree "39".
• Hales–Jewett_theorem wikiPageRevisionID "674176383".
• Hales–Jewett_theorem wikiPageWikiLink Ackermann_function.
• Hales–Jewett_theorem wikiPageWikiLink Alfred_W._Hales.
• Hales–Jewett_theorem wikiPageWikiLink Argument.
• Hales–Jewett_theorem wikiPageWikiLink Arithmetic_progression.
• Hales–Jewett_theorem wikiPageWikiLink Bartel_Leendert_van_der_Waerden.
• Hales–Jewett_theorem wikiPageWikiLink Category:Articles_containing_proofs.
• Hales–Jewett_theorem wikiPageWikiLink Category:Ramsey_theory.
• Hales–Jewett_theorem wikiPageWikiLink Category:Theorems_in_discrete_mathematics.
• Hales–Jewett_theorem wikiPageWikiLink Combinatorics.
• Hales–Jewett_theorem wikiPageWikiLink Corners_theorem.
• Hales–Jewett_theorem wikiPageWikiLink Decimal.
• Hales–Jewett_theorem wikiPageWikiLink Ergodic_theory.
• Hales–Jewett_theorem wikiPageWikiLink Hypercube.
• Hales–Jewett_theorem wikiPageWikiLink Mathematical_induction.
• Hales–Jewett_theorem wikiPageWikiLink Mathematics.
• Hales–Jewett_theorem wikiPageWikiLink Pigeonhole_principle.
• Hales–Jewett_theorem wikiPageWikiLink Polymath_Project.
• Hales–Jewett_theorem wikiPageWikiLink Primitive_recursive_function.
• Hales–Jewett_theorem wikiPageWikiLink Proof_by_contradiction.
• Hales–Jewett_theorem wikiPageWikiLink Ramsey_theory.
• Hales–Jewett_theorem wikiPageWikiLink Saharon_Shelah.
• Hales–Jewett_theorem wikiPageWikiLink Strategy-stealing_argument.
• Hales–Jewett_theorem wikiPageWikiLink Szemerxc3xa9dis_theorem.
• Hales–Jewett_theorem wikiPageWikiLink Tic-tac-toe.
• Hales–Jewett_theorem wikiPageWikiLink Van_der_Waerdens_theorem.
• Hales–Jewett_theorem wikiPageWikiLinkText "Hales–Jewett theorem".
• Hales–Jewett_theorem wikiPageWikiLinkText "Hales–Jewett number".
• Hales–Jewett_theorem wikiPageWikiLinkText "Hales–Jewett theorem".
• Hales–Jewett_theorem subject Category:Articles_containing_proofs.
• Hales–Jewett_theorem subject Category:Ramsey_theory.
• Hales–Jewett_theorem subject Category:Theorems_in_discrete_mathematics.
• Hales–Jewett_theorem hypernym Result.
• Hales–Jewett_theorem type Combinatoric.
• Hales–Jewett_theorem type Proof.
• Hales–Jewett_theorem type Redirect.
• Hales–Jewett_theorem type Theorem.
• Hales–Jewett_theorem comment "In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I.".
• Hales–Jewett_theorem label "Hales–Jewett theorem".
• Hales–Jewett_theorem sameAs Q1032886.
• Hales–Jewett_theorem sameAs Halesova-Jewettova_věta.
• Hales–Jewett_theorem sameAs قضیه_هیلز–جووت.
• Hales–Jewett_theorem sameAs Hales–Jewett-tétel.
• Hales–Jewett_theorem sameAs 헤일스-주잇_정리.
• Hales–Jewett_theorem sameAs m.02zm_k.
• Hales–Jewett_theorem sameAs Q1032886.
• Hales–Jewett_theorem wasDerivedFrom Hales–Jewett_theorem?oldid=674176383.
• Hales–Jewett_theorem isPrimaryTopicOf Hales–Jewett_theorem.