Page 1

Displaying 1 – 14 of 14

Showing per page

More on the complexity of cover graphs

Jaroslav Nešetřil, Vojtěch Rödl (1995)

Commentationes Mathematicae Universitatis Carolinae

In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.

More set-theory around the weak Freese–Nation property

Sakaé Fuchino, Lajos Soukup (1997)

Fundamenta Mathematicae

We introduce a very weak version of the square principle which may hold even under failure of the generalized continuum hypothesis. Under this weak square principle, we give a new characterization (Theorem 10) of partial orderings with κ-Freese-Nation property (see below for the definition). The characterization is not a ZFC theorem: assuming Chang’s Conjecture for ω , we can find a counter-example to the characterization (Theorem 12). We then show that, in the model obtained by adding Cohen reals,...

Currently displaying 1 – 14 of 14

Page 1