When no single universal model for a set of structures exists at a given cardinal, then one may ask in which models of set theory does there exist a small family which embeds the rest. We show that for λ+-graphs (λ regular) omitting cliques of some finite or uncountable cardinality, it is consistent that there are small universal families and 2λ > λ+. In particular, we get such a result for triangle-free graphs.

This paper will examine universality spectra for relational theories which cannot be described in first-order logic. We will give a method using functors to show that two types of structures have the same universality spectrum. A combination of methods will be used to show universality results for certain ordered structures and graphs. In some cases, a universal spectrum under GCH will be obtained. Since the theories are not first-order, the classic model theory result under GCH does not hold.

Analogues of Ramsey’s Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the author’s recent result for the triangle-free Henson graph, we prove (...) that for each [Formula: see text], the k-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey’s Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker. (shrink)

If [Formula: see text] is a closed Noetherian graph on a [Formula: see text]-compact Polish space with no infinite cliques, it is consistent with the choiceless set theory ZF[Formula: see text][Formula: see text][Formula: see text]DC that [Formula: see text] is countably chromatic and there is no Vitali set.

Community detection is a major issue in network analysis. This paper combines a socio-historical approach with an experimental reconstruction of programs to investigate the early automation of clique detection algorithms, which remains one of the unsolved NP-complete problems today. The research led by the archaeologist Jean-Claude Gardin from the 1950s on non-numerical information and graph analysis is retraced to demonstrate the early contributions of social sciences and humanities. The limited recognition and reception of Gardin's innovative computer application to the humanities (...) are addressed through two factors, in addition to the effects of historiography and bibliographies on the recording, discoverability, and reuse of scientific productions: (1) funding policies, evidenced by the transfer of research effort on graph applications from temporary interdisciplinary spaces to disciplinary organizations related to the then-emerging field of computer science; and (2) the erratic careers of algorithms, in which efficiency, flaws, corrections, and authors’ status, were determining factors. (shrink)

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math.38(1) (1971) 69–83] and denoted H3, is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.I, eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and (...) culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica26(2) (2006) 183–205], the Ramsey theory of H3 had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin.2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math.185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph G, there is a finite number T(G) such that for any coloring of all copies of G in H3 into finitely many colors, there is a subgraph of H3 which is again universal homogeneous triangle-free in which the coloring takes no more than T(G) colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code H3 and the development of their Ramsey theory. (shrink)

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture : ‘there is a number a>0 such that for all (...) k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant . Let P be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G1,G2,…,GN are unlabelled planar graphs with Gishrink)

For automatic and recursive graphs, we investigate the following problems: (A) existence of a Hamiltonian path and existence of an infinite path in a tree (B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree (C) existence of an infinite clique and an infinite version of set cover The complexity of these problems is determined for automatic graphs and, supplementing results from the literature, for recursive graphs. (...) Our results show that these problems (A) are equally complex for automatic and for recursive graphs ( $\Sigma _{1}^{1}\text{-complete}$ ), (B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy), (C) are much simpler for automatic than for recursive graphs (decidable and $\Sigma _{1}^{1}\text{-complete}$ , resp.). (shrink)

Given a finite relational language L is there an algorithm that, given two finite sets A and B of structures in the language, determines how many homogeneous L structures there are omitting every structure in B and embedding every structure in A? For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether QΓ, the class of finite tournaments omitting every tournament in Γ, is well-quasi-order? First, we (...) give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere. The case in which Γ consists of two tournaments is also discussed. (shrink)

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G -independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a (...) Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ1. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA.Slightly weaker results hold for Fσ-graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable Fσ-graph has a Borel chromatic number of at most ℵ1.We refute various reasonable generalizations of these results to hypergraphs. (shrink)

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. Using interpolation we establish an exponential-size lower bound on refutations in a certain, considerably strong, fragment of resolution over linear equations, as well as a general polynomial upper bound on interpolants (...) in this fragment.We then apply these results to extend and improve previous results on multilinear proofs , as studied in [Ran Raz, Iddo Tzameret, The strength of multilinear proofs. Comput. Complexity ]. Specifically, we show the following:• Proofs operating with depth-3 multilinear formulas polynomially simulate a certain, considerably strong, fragment of resolution over linear equations.• Proofs operating with depth-3 multilinear formulas admit polynomial-size refutations of the pigeonhole principle and Tseitin graph tautologies. The former improve over a previous result that established small multilinear proofs only for the functional pigeonhole principle. The latter are different from previous proofs, and apply to multilinear proofs of Tseitin mod p graph tautologies over any field of characteristic 0. We conclude by connecting resolution over linear equations with extensions of the cutting planes proof system. (shrink)

We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most (...) k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle. Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result. (shrink)

We study repeated normal form games where the number of players is large. We argue that it is interesting to look at such games as being divided into subgames, each of which we call a neighbourhood. The structure of such a game is given by a graph G whose nodes are players and edges denote visibility. The neighbourhoods are maximal cliques in G. The game proceeds in rounds where in each round the players of every clique X of G (...) play a strategic form game among each other. A player at a node v strategises based on what she can observe, i.e., the strategies and the outcomes in the previous round of the players at vertices adjacent to v. Based on this, the player may switch strategies in the same neighbourhood, or migrate to another neighbourhood.We are interested in addressing questions regarding the eventual stability of such games. We incrementally impose constraints on the ‘types’ of the players. First, we look at players who are unconstrained in their strategising abilities, in that, players who may use unbounded memory. We then consider the case of memoryless players. We show that in both these cases the eventual stability of the game can be characterised in terms of potentials. We then introduce a simple modal logic in which the types of the players can be specified. We show that when the players play according to these specified types, it can be effectively decided whether the game stabilises. Finally, we look at the important heuristic of imitation. Simple imitative strategies can be specified in the logic introduced by us. We show that in a population of optimisers and imitators, we can decide how ‘worse-off’ the imitators are by playing imitative strategies rather than optimal ones. (shrink)

We make comments on some problems Erdős and Hajnal posed in their famous problem list. Let X be a graph on $\omega _1$ with the property that every uncountable set A of vertices contains a finite set s such that each element of $A-s$ is joined to one of the elements of s. Does then X contain an uncountable clique? We prove that both the statement and its negation are consistent. Do there exist circuitfree graphs $\{X_n:n<\omega \}$ on $\omega (...) _1$ such that if $A\in [\omega _1]^{\aleph _1}$, then $\{n<\omega :X_n\cap [A]^2=\emptyset \}$ is finite? We show that the answer is yes under CH, and no under Martin’s axiom. Does there exist $F:[\omega _1]^2\to 3$ with all three colors appearing in every uncountable set, and with no triangle of three colors. We give a different proof of Todorcevic’ theorem that the existence of a $\kappa $ -Suslin tree gives $F:[\kappa ]^2\to \kappa $ establishing $\kappa \not \to [\kappa ]^2_{\kappa }$ with no three-colored triangles. This statement in turn implies the existence of a $\kappa $ -Aronszajn tree. (shrink)

A Ramsey statement denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \longrightarrow (k)^2_2}$$\end{document} says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(nk) and with terms of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$$\end{document}. Let rk be the minimal n for which the statement holds. We prove that (...) RAM(rk, k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák’s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4k, k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Philosophy and Literature 26.1 (2002) 224-238 [Access article in PDF] Bookmarks A Hanging Judge Denis Dutton "CORNERING THE MARKET ON CHUTZPAH," blared the headline on one review, and in tone it wasn't alone. It's not often that a book by a public intellectual has received as much media attention—mostly vilification and scorn—as Richard A. Posner's Public Intellectuals: A Study of Decline (Harvard University Press, $29.95). Three reasons for this (...) stand out. First, there's the sheer audacity of including a list of the top hundred public intellectuals, drawn from a larger list of 546 names. This invites endless dispute over how the list was generated, who is on it, who is left off, where each one stands, and why. Second, there is the fact that Posner has managed in the book to offend half of the public intellectuals you'd expect to be called on to review it—almost as though he made a list of potential reviewers and worked in a swipe at each. Finally, he has tapped into the deep antipathy humanist intellectuals have to seeing a beloved topic treated quantitatively, with statistics and applications of social and economic theory, replete with graphs and algebraic formulae. And after all, what topic is more beloved by the intellectuals than they themselves? That Posner would actually treat such important people as a demographic type, sorting them in terms of race, age, field, politics, sex—why, he even asks why so many are Jews. It's outrageous... and delicious.Definitions first. The idea of an intellectual, Posner says, should not be identified merely with having highbrow, cultivated tastes, being especially creative, or having high intelligence. All of these things are possible without being an intellectual, which Posner thinks ought to denote the application of the mind to "political matters in the broadest sense of that word, a sense that includes cultural matters when they are [End Page 224] viewed under the aspect of ideology, ethics, or politics (which may all be the same thing)." There is therefore a vague redundancy in the term "public intellectual," since the placing of ideas in a larger public context, acting as social critic, is what the intellectual most essentially does. In our age of vast communication media, it is also done con-spicuously in public, through op-eds, public radio interviews, and on TV clips with the regulation public-intellectual bookcase as a backdrop. This concern with larger moral issues means that for Posner paradigm individuals would therefore include the likes of John Dewey, Bertrand Russell, Hannah Arendt, Arthur Koestler, Edmund Wilson, Susan Sontag, and most powerfully in Posner's mind, George Orwell: people who write about literature, art, science, and so forth from a broadly political or ideological perspective. For example, when Allan Bloom writes about rock and roll, he is not doing so as a music critic but as a philosopher who sees it as a symptom and source of social degradation. That's echte public intellectual work (and rather bad work in this particular case, Posner believes). That it is done for a broader public is also a crux for Posner, who leaves omits John Rawls from his list, because as influential as Rawls is as a philosopher, he does not address a larger public in the way that Richard Rorty and Martha Nussbaum do.The decline referred to in Posner's title is a decline in the actual worth of public intellectuals' work, not in their media celebrity, which has grown roughly inversely to the value of what they do. This invidious situation has followed, in Posner's view, the proliferation of academics in the ranks of public intellectuals. From the nineteenth century, with such names as Thoreau, J. S. Mill, Herbert Spencer, Matthew Arnold, and Tocqueville, to well into the twentieth, with the likes of Max Eastman, Edmund Wilson, H. G. Wells, and Dwight Macdonald, the great tradition of public intellectuals had its life outside of universities. Although there remain nonacademic public intellectuals today—Susan Sontag, Roger Kimball, Tom Wolfe, Gore Vidal—they are a severely diminished species. Universities, which have expanded... (shrink)

Description logic knowledge bases can be used to represent knowledge about a particular domain in a formal and unambiguous manner. Their practical relevance has been shown in many research areas, especially in biology and the Semantic Web. However, the tasks of constructing knowledge bases itself, often performed by human experts, is difficult, time-consuming and expensive. In particular the synthesis of terminological knowledge is a challenge that every expert has to face. Because human experts cannot be omitted completely from the construction (...) of knowledge bases, it would therefore be desirable to at least get some support from machines during this process. To this end, we shall investigate in this work an approach which shall allow us to extract terminological knowledge in the form of general concept inclusions from factual data, where the data is given in the form of vertex- and edge-labelled graphs. Because such graphs appear naturally within the scope of the Semantic Web in the form of sets of Resou... (shrink)

The problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in the category of graphs with a vertex coloring by two colors. It is not known whether this problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable.

In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction. In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian (...) class='Hi'>graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE. (shrink)

The aim of our paper is to present noun phrase ellipsis as a cohesive tie in the Macedonian language. We will start our paper briefly discussing a few definitions of the term ellipsis, emphasizing our understanding of this term, and more concretely its meaning when occurring in the NP. Namely, we define ellipsis as a complex phenomenon. In linguistics, it means the omitting of linguistic elements that need to be understood from the context, where the recipient should adequately fill (...) the grammatically allowable gap. Then we will refer to different kinds of ellipsis in Macedonian, starting with our main issue - ellipsis in the noun phrase. Elliptical NP is cohesive and usually refers anaphorically to another NP. But the main question is how much of the full noun phrase is involved in the elliptical NP in Macedonian. For that purpose, we will analyze examples to define which elements of the NP can be omitted and under which conditions. Examples of cataphoric ellipsis are also included. When there is an ellipsis of the center of the phrase, the other element of the NP functions as the center of the phrase. For more precision research, we will use examples of different functional styles in Macedonian. The examples will be given first in Macedonian, and then translated into English. Our conclusion will be presented through graphs. (shrink)

Cohesion may be based primarily on interpersonal ties or rely instead on the connection between member and group, while groups may cohere temporarily based on the immediate alignment of interests among members or may be tied together more permanently by socio-emotional bonds. Together, these characteristics define four prototypical group types. Cliques and coalitions are based primarily on dyadic ties. Groups of comrades or colleagues rely instead on the connection of members to the group for cohesion, which reduces the marginal (...) cost of increasing group size. The strong glue of socio-emotional cohesion binds cliques and comrades, while coalitions and groups of colleagues are often based on weaker forms of cohesion. The mix of strong and weak adhesives and the greater scalability offered by the member-group bond provide the building blocks for assembling very large societies without overtaxing the social brain. (shrink)

This chapter contains sections titled: Ways of Failing to Do Something Refraining Omitting Negative Acts: Inaction as Action? References.

We introduce a framework for a graph-theoretic analysis of the semantic paradoxes. Similar frameworks have been recently developed for infinitary propositional languages by Cook and Rabern, Rabern, and Macauley. Our focus, however, will be on the language of first-order arithmetic augmented with a primitive truth predicate. Using Leitgeb’s notion of semantic dependence, we assign reference graphs (rfgs) to the sentences of this language and define a notion of paradoxicality in terms of acceptable decorations of rfgs with truth values. It (...) is shown that this notion of paradoxicality coincides with that of Kripke. In order to track down the structural components of an rfg that are responsible for paradoxicality, we show that any decoration can be obtained in a three-stage process: first, the rfg is unfolded into a tree, second, the tree is decorated with truth values (yielding a dependence tree in the sense of Yablo), and third, the decorated tree is re-collapsed onto the rfg. We show that paradoxicality enters the picture only at stage three. Due to this we can isolate two basic patterns necessary for paradoxicality. Moreover, we conjecture a solution to the characterization problem for dangerous rfgs that amounts to the claim that basically the Liar- and the Yablo graph are the only paradoxical rfgs. Furthermore, we develop signed rfgs that allow us to distinguish between ‘positive’ and ‘negative’ reference and obtain more fine-grained versions of our results for unsigned rfgs. (shrink)

Hyperlink cinema is an emergent film genre that seeks to push the boundaries of the medium in order to mirror contemporary life in the globalized community. Films in the genre thus create an interacting network across space and time in such a way as to suggest that people’s lives can intersect on scales that would not have been possible without modern technologies of travel and communication. This allows us to test the hypothesis that new kinds of media might permit us (...) to break through the natural cognitive constraints that limit the number and quality of social relationships we can manage in the conventional face-to-face world. We used network analysis to test this hypothesis with data from 12 hyperlink films, using 10 motion pictures from a more conventional film genre as a control. We found few differences between hyperlink cinema films and the control genre, and few differences between hyperlink cinema films and either the real world or classical drama (e.g., Shakespeare’s plays). Conversation group size seems to be especially resilient to alteration. It seems that, despite many efficiency advantages, modern media are unable to circumvent the constraints imposed by our evolved psychology. (shrink)

Modeling mechanisms is central to the biological sciences – for purposes of explanation, prediction, extrapolation, and manipulation. A closer look at the philosophical literature reveals that mechanisms are predominantly modeled in a purely qualitative way. That is, mechanistic models are conceived of as representing how certain entities and activities are spatially and temporally organized so that they bring about the behavior of the mechanism in question. Although this adequately characterizes how mechanisms are represented in biology textbooks, contemporary biological research practice (...) shows the need for quantitative, probabilistic models of mechanisms, too. In this paper we argue that the formal framework of causal graph theory is well-suited to provide us with models of biological mechanisms that incorporate quantitative and probabilistic information. On the ba-sis of an example from contemporary biological practice, namely feedback regulation of fatty acid biosynthesis in Brassica napus, we show that causal graph theoretical models can account for feedback as well as for the multi-level character of mechanisms. However, we do not claim that causal graph theoretical representations of mechanisms are advantageous in all respects and should replace common qualitative models. Rather, we endorse the more balanced view that causal graph theoretical models of mechanisms are useful for some purposes, while being insufficient for others. (shrink)

This paper is about omitting types in logic of metric structures introduced by Ben Yaacov, Berenstein, Henson and Usvyatsov. While a complete type is omissible in some model of a countable complete...

I argue that Frege Problems in thought are best modeled using graph-theoretic machinery; and that these problems can arise even when subjects associate all the same qualitative properties to the object they’re thinking of twice. I compare the proposed treatment to similar ideas by Heck, Ninan, Recanati, Kamp and Asher, Fodor, and others.

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

In this paper, an extension of first order logic is introduced. In such logics atomic formulas may have infinite lengths. An Omitting Types Theorem is proved.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first (...) order logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

The graph edit distance (GED) measures the dissimilarity between two graphs as the minimal cost of a sequence of elementary operations transforming one graph into another. This measure is fundamental in many areas such as structural pattern recognition or classification. However, exactly computing GED is NP-hard. Among different classes of heuristic algorithms that were proposed to compute approximate solutions, local search based algorithms provide the tightest upper bounds for GED. In this paper, we present K-REFINE and RANDPOST. K-REFINE generalizes (...) and improves an existing local search algorithm and performs particularly well on small graphs. RANDPOST is a general warm start framework that stochastically generates promising initial solutions to be used by any local search based GED algorithm. It is particularly efficient on large graphs. An extensive empirical evaluation demonstrates that both K-REFINE and RANDPOST perform excellently in practice. (shrink)

Peirce considered the principal business of logic to be the analysis of reasoning. He argued that the diagrammatic system of Existential Graphs, which he had invented in 1896, carries the logical analysis of reasoning to the furthest point possible. The present paper investigates the analytic virtues of the Alpha part of the system, which corresponds to the sentential calculus. We examine Peirce’s proposal that the relation of illation is the primitive relation of logic and defend the view that this (...) idea constitutes the fundamental motive of philosophy of notation both in algebraic and graphical logic. We explain how in his algebras and graphs Peirce arrived at a unifying notation for logical constants that represent both truth-function and scope. Finally, we show that Shin’s argument for multiple readings of Alpha graphs is circular. (shrink)

Can you find an xy-equation that, when graphed, writes itself on the plane? This idea became internet-famous when a Wikipedia article on Tupper’s self-referential formula went viral in 2012. Under scrutiny, the question has two flaws: it is meaningless (it depends on fonts) and it is trivial. We fix these flaws by formalizing the problem.

In this paper, we analyze and discuss Schopenhauer’s n-term diagrams for eristic dialectics from a graph-theoretical perspective. Unlike logic, eristic dialectics does not examine the validity of an isolated argument, but the progression and persuasiveness of an argument in the context of a dialogue or even controversy. To represent these dialogue situations, Schopenhauer created large maps with concepts and Euler-type diagrams, which from today’s perspective are a specific form of graphs. We first present the original method with Euler-type diagrams, (...) then give the most important graph-theoretical definitions, then discuss Schopenhauer’s diagrams graph-theoretically and finally give an example of how the graphs or diagrams can be used to analyze dialogues. (shrink)

The paper is concerned with the existence of a universal graph at the successor of a strong limit singular μ of cofinality ℵ0. Starting from the assumption of the existence of a supercompact cardinal, a model is built in which for some such μ there are $\mu^{++}$ graphs on μ+ that taken jointly are universal for the graphs on μ+, while $2^{\mu^+} \gg \mu^{++}$ . The paper also addresses the general problem of obtaining a framework for consistency results (...) at the successor of a singular strong limit starting from the assumption that a supercompact cardinal κ exists. The result on the existence of universal graphs is obtained as a specific application of a more general method. (shrink)

We study a class of [0,1][0,1]-valued logics. The main result of the paper is a maximality theorem that characterizes these logics in terms of a model-theoretic property, namely, an extension of the omitting types theorem to uncountable languages.

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an (...) effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

We define a model for computing probabilities of right-nested conditionals in terms of graphs representing Markov chains. This is an extension of the model for simple conditionals from Wójtowicz and Wójtowicz. The model makes it possible to give a formal yet simple description of different interpretations of right-nested conditionals and to compute their probabilities in a mathematically rigorous way. In this study we focus on the problem of the probabilities of conditionals; we do not discuss questions concerning logical and (...) metalogical issues such as setting up an axiomatic framework, inference rules, defining semantics, proving completeness, soundness etc. Our theory is motivated by the possible-worlds approach ; however, our model is generally more flexible. In the paper we focus on right-nested conditionals, discussing them in detail. The graph model makes it possible to account in a unified way for both shallow and deep interpretations of right-nested conditionals. In particular, we discuss the status of the Import-Export Principle and PCCP. We briefly discuss some methodological constraints on admissible models and analyze our model with respect to them. The study also illustrates the general problem of finding formal explications of philosophically important notions and applying mathematical methods in analyzing philosophical issues. (shrink)

It is a widespread assumption in philosophy of science that data is what is explained by theory—that data itself is not explanatory. I draw on instances of representational and explanatory practice from mammalian chronobiology to suggest that this assumption is unsustainable. In many instances, biologists employ representations of data in explanatory ways that are not reducible to constraints on or evidence for representations of mechanisms. Data graphs are used to exemplify relationships between quantities in the mechanism, and often these (...) representations are necessary for explaining particular aspects of the phenomena under study. I argue that this kind of representation is distinct from representing laws or generalizations, and its primary purpose is to convey particular types or patterns of quantitative relationships. The benefit of the analysis is two-fold. First, it provides a more accurate account of explanatory practice in broadly mechanistic analysis in biology. Second, it suggests that there is not an explanatory “fundamental” type of representation in biology. Rather, the practice of explanation consists in the construction of different types of representations and their employment for distinct explanatory purposes. (shrink)

We describe Peirce’s 1903 system of modal gamma graphs, its transformation rules of inference, and the interpretation of the broken-cut modal operator. We show that Peirce proposed the normality rule in his gamma system. We then show how various normal modal logics arise from Peirce’s assumptions concerning the broken-cut notation. By developing an algebraic semantics we establish the completeness of fifteen modal logics of gamma graphs. We show that, besides logical necessity and possibility, Peirce proposed an epistemic interpretation (...) of the broken-cut modality, and that he was led to analyze constructions of knowledge in the style of epistemic logic. (shrink)

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

We prove that the classes of UHF algebras and AF algebras, while not axiomatizable, can be characterized as those C*-algebras that omit certain types in the logic of metric structures.

This paper introduces a class of graphical independence models that is closed under marginalization and conditioning but that contains all DAG independence models. This class of graphs, called maximal ancestral graphs, has two attractive features: there is at most one edge between each pair of vertices; every missing edge corresponds to an independence relation. These features lead to a simple parameterization of the corresponding set of distributions in the Gaussian case.

Peirce and Frege both distinguished between the propositional content of an assertion and the assertion of a propositional content, but with different notational means. We present a modification of Peirce’s graphical method of logic that can be used to reason about assertions in a manner similar to Peirce’s original method. We propose a new system of Assertive Graphs, which unlike the tradition that follows Frege involves no ad hoc sign of assertion. We show that axioms of intuitionistic logic can (...) be derived from AGs, and argue that AGs analyse and represent assertions and illocutionary content in a way which is motivated both by its logical properties and its historical connection with the ideas that led to the development of the graphical method. (shrink)

In this paper we propose an non-machine learning artificial intelligence (AI) based approach for telecom data analysis, with a special focus on clique detection. Clique detection can be used to identify households, which is a major challenge in telecom data analysis and predictive analytics. Our approach does not use any form of machine learning, but another type of algorithm: satisfiability for propositional logic. This is a neglected approach in modern AI, and we aim to demonstrate that for certain tasks, it (...) may be a good alternative to machine learning-based approaches. We have used a simple DPLL satisfiability solver over an artificially generated telecom dataset (due to GDPR regulations), but our approach can be implemented on any telecom data by following the SAT encoding we have developed, and the DPLL solver can be substituted by a more advanced alternative such as CDCL. This paper extends the method presented in [1] for banking logs to data containing caller information, and proposes a more efficient encoding. -/- . (shrink)

We consider a problem of constructing a model that omits given complete types. We present two results. The first one is related to the Lopez-Escobar theorem and the second one is a version of Morley's omitting types theorem.