Finite forbidden-pattern axiomatization Created 2026-09-24 Updated 2026-11-05
A finite forbidden relational pattern can be excluded by a universal sentence. If a finite structure has distinct vertices , let say that the variables are distinct and have the required relations. Then
forbids that pattern. Taking one sentence for each forbidden finite pattern gives a universal first-order theory.
For a triangle-free graph, the forbidden diagram asserts that three distinct vertices are pairwise adjacent. To forbid an induced pattern, the diagram must specify absent relations as well as present ones. Forbidding an ordinary path on three vertices allows extra edges between its vertices; forbidding an induced path on three vertices does not. Thus the meaning of pattern determines the exact diagram. The construction explains why many local graph constraints are preserved under taking substructures.