Omodeo, Eugenio G.; Policriti, Alberto; Tomescu, Alexandru I. On sets and graphs. Perspectives on logic and combinatorics. (English) Zbl 1382.05002 Cham: Springer (ISBN 978-3-319-54980-4/hbk; 978-3-319-54981-1/ebook). xix, 275 p. (2017). Why graphs? Without a good mastery of graphs, the design and analysis of computer algorithms would be unaffordable.Why sets? Set theory is commonly, though often implicitly, placed in the background of any other mathematical disciplines.This monograph looks into the relationship between sets and graphs from different points of view. The authors of this book examine the interplay of sets and graphs on a fairly fundamental level, formulating their set theory very carefully in such a way that some of the proofs become accessible to a set-based proof checker Referee. For the reader’s convenience a brief introduction of Referee is also provided here.In the introductory chapter, the authors use a large number of examples to explain the motivation to define correspondences between sets and graphs. The rest of the book is divided into three parts. Part I consists of Chapters 2 and 3 and it is all about basics. Chapters 4 and 5 belong to Part II. Here, the authors explain under what circumstances, and how, sets can conveniently model graphs, namely set graphs. Set graphs are undirected and connected and are topic of Chapter 4. They show here, that the class of set graphs contains traceable and claw-free graphs, too. Further, they establish that, although the set graphs are undirected, for a given undirected graph it is an NP-complete problem to check whether or not it is a set graph. Chapter 5 deals with directed graphs, too. The proofs of some of the results are verified here using Referee. Part III investigates the converse issue: when is it convenient to represent sets by graphs? It consists of Chapters 6, 7 and 8. The first two are mainly about finite sets while Chapter 8 deals with infinite sets. The topic of Chapter 7 is the generation of sets of size \(n\), uniformly at random. Three techniques are being used for this purpose. The first two methods are based on combinatorial decomposition while the third is based on Markov chains. Chapter 8 deals with the set-satisfiability problem. Reviewer: Ayesha Shabbir (Gurjat) Cited in 5 Documents MSC: 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics 03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations 03E05 Other combinatorial set theory 03E75 Applications of set theory 05C05 Trees 05C38 Paths and cycles 05C40 Connectivity 05C45 Eulerian and Hamiltonian graphs 05C63 Infinite graphs 05C65 Hypergraphs 05C90 Applications of graph theory 68R10 Graph theory (including graph drawing) in computer science 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:sets; set graphs; membership graphs; block graphs; claw-free graphs; directed graphs; undirected graphs; Hamiltonian path; Hamiltonian cycle; acyclic orientations; extensionalizations; infinities; choice axiom; Zermelo-Frankel axioms; NP-completeness; NP-hardness; Markov chain; proof checker; Referee; well-ordering; Ackermann encoding; computational complexity; hereditary finite sets; hypersets PDFBibTeX XMLCite \textit{E. G. Omodeo} et al., On sets and graphs. Perspectives on logic and combinatorics. Cham: Springer (2017; Zbl 1382.05002) Full Text: DOI