𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Universal tilings and universal (0,1)-matrices

✍ Scribed by C.R.J. Clapham

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
319 KB
Volume
58
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A periodic regular tiling of the plane by black and white squares is k-universal if it contains all possible k x k blocks of black and white tiles. There is a 4 x 4 periodic tiling that is 2-universal; this paper looks for the smallest 3-universal tiling and obtains a 64 x 32 periodic tiling that is 3-universal.

Related to this is the following: a (0, 1)-matrix is k-universal if every possible k x k (0, 1)-matrix occurs as a submatrix. It is proved that, for k even, there is a k2 ~ by k2 k/2 matrix that is k-universal and, for k odd, there is a (3k + 1)2 (k-3)/2 by (3k -1)2 (k-3)/2 matrix that is k-universal.

πŸ“œ SIMILAR VOLUMES

Universal tilings of the plane by 0–1-ma
Universal tilings of the plane by 0–1-matrices
✍ Knut Dehnhardt; Heiko Harborth πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 673 KB

A tiling of the plane by black and white unit squares of the square lattice is called (a, b)-universal if the tiling is built up by horizontal and vertical translations of a fundamental (m, n)-rectangle, and if every one of the possible 2ub different (a, b)-rectangles of black and white unit squares

Universal Properties of Infinite Matrice
Universal Properties of Infinite Matrices
✍ Roy O. Davies; Michael P. Drazin; Mark L. Roberts πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 148 KB
Universal graphs and induced-universal g
Universal graphs and induced-universal graphs
✍ Fan R. K. Chung πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 484 KB

## Abstract We construct graphs that contain all bounded‐degree trees on __n__ vertices as induced subgraphs and have only __cn__ edges for some constant __c__ depending only on the maximum degree. In general, we consider the problem of determining the graphs, so‐called universal graphs (or induced

Universal Induction and True Universal A
Universal Induction and True Universal Arithmetic
✍ Teresa Bigorajska πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 148 KB

## Abstract We prove that every finitely generated (as a ring) model for induction for universal formulas without parameters satisfies also all true universal sentences. Mathematics Subject Classification: 03C62.