De Bruijn torus

De Bruijn torus: A De Bruijn torus. Each 2-by-2 binary matrix can be found within it exactly once.

In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains every m-by-n matrix exactly once. It is a torus because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence, which can be considered a special case where n is 1 (one dimension).

One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given m and n. It is known that these always exist when n = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever m = n.^[1]

References

^ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sept. 2009). "Research problems on Gray codes and universal cycles". Discrete Mathematics 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.

Categories:
Combinatorics

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

De Bruijn sequence — A diagram showing the De Bruijn sequence where k=2 and n=2 In combinatorial mathematics, a k ary De Bruijn sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A … Wikipedia
De Bruijn — is a Dutch surname. It may refer to: Chantal de Bruijn Cornelis de Bruijn, Dutch artist and traveler Daniëlle de Bruijn Inge de Bruijn, Dutch swimmer Nicolaas Govert de Bruijn, Dutch mathematician Maarten de Bruijn Nick de Bruijn Pi de Bruijn In… … Wikipedia
Digital paper — Digital paper, also known as interactive paper, is patterned paper used in conjunction with a digital pen to create handwritten digital documents.[1] The printed dot pattern uniquely identifies the position coordinates on the paper. The digital… … Wikipedia
List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… … Wikipedia
Four color theorem — Example of a four colored map A four colori … Wikipedia
Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… … Wikipedia
Evenness of zero — The number 0 is even. There are several ways to determine whether an integer is even or odd, all of which indicate that 0 is an even number: it is a multiple of 2, it is evenly divisible by 2, it is surrounded on both sides by odd integers, and… … Wikipedia

Academic Dictionaries and Encyclopedias

De Bruijn torus

References

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

De Bruijn torus

References

Look at other dictionaries:

Share the article and excerpts

Direct link