# Sh:611

• Rosen, E., Shelah, S., & Weinstein, S. (1997). k-universal finite graphs. In Logic and random structures (New Brunswick, NJ, 1995), Vol. 33, Amer. Math. Soc., Providence, RI, pp. 65–77.
• Abstract:
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.
Bib entry
@incollection{Sh:611,
author = {Rosen, Eric and Shelah, Saharon and Weinstein, Scott},
title = {{$k$-universal finite graphs}},
booktitle = {{Logic and random structures (New Brunswick, NJ, 1995)}},
series = {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.},
volume = {33},
year = {1997},
pages = {65--77},
mrclass = {03C13 (03C75 05C99)},
mrnumber = {1465469},
mrreviewer = {M. Yasuhara},
publisher = {Amer. Math. Soc., Providence, RI},
note = {\href{https://arxiv.org/abs/math/9604244}{arXiv: math/9604244}},
arxiv_number = {math/9604244}
}