### $k$--Universal Finite Graphs

by Rosen and Shelah and Weinstein. [RShW:611]

Logic and Random Structures: DIMACS Workshop, November 5-7, 1995, 1997

This paper investigates the class of k-universal finite
graphs, a local analog of the class of universal graphs, which
arises naturally in the study of finite variable logics. The main
results of the paper, which are due to Shelah, establish that the
class of k-universal graphs is not definable by an infinite
disjunction of first-order existential sentences with a finite
number of variables and that there exist k-universal graphs with
no k-extendible induced subgraphs.

Back to the list of publications