We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).

We explain and summarize the use of logic to provide a uniform perspective for studying limit laws on finite probability spaces. This work connects developments in stability theory, finite model theory, abstract model theory, and probability. We conclude by linking this context with work on the Urysohn space.

Ideas from random graph theory are used to give an heuristic argument that associative memory structure depends discontinuously on pattern recognition ability. This argument suggests that there may be a certain minimal size for intelligent systems.

We introduce the subject of modal model theory, where one studies a mathematical structure within a class of similar structures under an extension concept that gives rise to mathematically natural notions of possibility and necessity. A statement φ is possible in a structure (written φ) if φ is true in some extension of that structure, and φ is necessary (written φ) if it is true in all extensions of the structure. A principal case for us will be the class (...) Mod(T) of all models of a given theory T—all graphs, all groups, all fields, or what have you—considered under the substructure relation. In this article, we aim to develop the resulting modal model theory. The class of all graphs is a particularly insightful case illustrating the remarkable power of the modal vocabulary, for the modal language of graph theory can express connectedness, k-colorability, finiteness, countability, size continuum, size ℵ1, ℵ2, ℵω, ℶω, first ℶ-fixed point, first ℶ-hyper-fixed point, and much more. A graph obeys the maximality principle φ(a)→φ(a) with parameters if and only if it satisfies the theory of the countable random graph, and it satisfies the maximality principle for sentences if and only if it is universal for finite graphs. (shrink)

Every set can been thought of as a directed graph whose edge relation is ∈. We show that many natural examples of directed graphs of this kind are indivisible: for every infinite κ, for every indecomposable λ, and every countable model of set theory. All of the countable digraphs we consider are orientations of the countable random graph. In this way we find indivisible well‐founded orientations of the random graph that are distinct up to (...) isomorphism, and ℵ1 that are distinct up to siblinghood. (shrink)

This chapter contains sections titled: Validity in the Finite Model Theory in the Finite? Definability and Complexity First‐Order Definability Second‐Order Definability Inductive Definability Infinitary Logics Random Graphs and 0–1 Laws.

In recent years, functional connectivity in the developmental science received increasing attention. Although it has been reported that the anatomical connectivity in the preterm brain develops dramatically during the last months of pregnancy, little is known about how functional and effective connectivity change with maturation. The present study investigated how effective connectivity in premature infants evolves. To assess it, we use EEG measurements and graph-theory methodologies. We recorded data from 25 preterm babies, who underwent long-EEG monitoring at least (...) twice during their stay in the NICU. The recordings took place from 27 weeks postmenstrual age until 42 weeks PMA. Results showed that the EEG-connectivity, assessed using graph-theory indices, moved from a small-world network to a random one, since the clustering coefficient increases and the path length decreases. This shift can be due to the development of the thalamocortical connections and long-range cortical connections. Based on the network indices, we developed different age-prediction models. The best result showed that it is possible to predict the age of the infant with a root mean-squared error equal to 2.11 weeks. These results are similar to the ones reported in the literature for age prediction in preterm babies. (shrink)

We show that the quantifier elimination result for the Shelah-Spencer almost sure theories of sparse random graphs $$G(n,n^{-\alpha })$$ given by Laskowski (Isr J Math 161:157–186, 2007) extends to their various analogues. The analogues will be obtained as theories of generic structures of certain classes of finite structures with a notion of strong substructure induced by rank functions and we will call the generics Baldwin–Shi hypergraphs. In the process we give a method of constructing extensions whose ‘relative rank’ is (...) negative but arbitrarily small in context. We give a necessary and sufficient condition for the theory of a Baldwin–Shi hypergraph to have atomic models. We further show that for certain well behaved classes of theories of Baldwin–Shi hypergraphs, the existentially closed models and the atomic models correspond. (shrink)

Countable homogeneous relational structures have been studied by many people. One area of focus is the Ramsey theory of such structures. After a review of background material, a partition theorem of Laflamme, Sauer, and Vuksanovic for countable homogeneous binary relational structures is discussed with a focus on the size of the set of unavoidable colors.

We use exact saturation to study the complexity of unstable theories, showing that a variant of this notion called pseudo-elementary class (PC)-exact saturation meaningfully reflects combinatorial dividing lines. We study PC-exact saturation for stable and simple theories. Among other results, we show that PC-exact saturation characterizes the stability cardinals of size at least continuum of a countable stable theory and, additionally, that simple unstable theories have PC-exact saturation at singular cardinals satisfying mild set-theoretic hypotheses. This had previously been open (...) even for the random graph. We characterize supersimplicity of countable theories in terms of having PC-exact saturation at singular cardinals of countable cofinality. We also consider the local analog of PC-exact saturation, showing that local PC-exact saturation for singular cardinals of countable cofinality characterizes supershort theories. (shrink)

We propose an original use of techniques from random graph theory to find a Monadic ∑ 1 1 sentence without an asymptotic probability. Our result implies that the 0-1 law fails for the logics ∑ 1 1 and ∑ 1 1 . Therefore we complete the classification of first-order prefix classes with or without equality, according to the existence of the 0-1 law for the corresponding ∑ 1 1 fragment. In addition, our counterexample can be viewed as (...) a single explanation of the failure of the 0-1 law of all the fragments of existential second-order logic for which the failure is already known. (shrink)

We investigate some dynamical features of the actions of automorphisms in the context of model theory. We interpret a few notions such as compact systems, entropy and symbolic representations from the theory of dynamical systems in the realm of model theory. In this direction, we settle a number of characterizations of NIP theories in terms of dynamics of automorphisms and invariant measures. For example, it is shown that the property of NIP corresponds to the compactness property of (...) some associated systems and also to the zero entropy property of automorphisms. These results give a correspondence between some notions of tameness in model theory and ergodic theory. Moreover, we study the concept of symbolic representation and consider it in some well known mathematical objects such as the circle group, Bohr sets, Sturmian sequences, the structure \\), and random graphs with a model theoretic point of view in mind. We establish certain characterizations for stability theoretic dividing lines, such as independence property, order property and strict order property in terms of associated symbolic representations. At the end, we propose some applications of symbolic representations and these characterizations by giving a proof for a classical theorem by Shelah and also introducing some invariants associated to the types and elements of models. (shrink)

In [9] we introduced a new framework for asymptotic probabilities, in which a $\sigma-additive$ measure is defined on the sample space of all sequences $A = $ of finite models, where the universe of An is {1, 2, .., n}. In this framework we investigated the strong 0-1 law for sentences, which states that each sentence either holds in An eventually almost surely or fails in An eventually almost surely. In this paper we define the strong convergence law for formulas, (...) which carries over the ideas of the strong 0-1 law to formulas with free variables, and roughly states that for each formula φ(x), the fraction of tuples a in An, which satisfy the formula φ(x), almost surely has a limit as n tends to infinity. We show that the infinitary logic with finitely many variables has the strong convergence law for formulas for the uniform measure, and further characterize the measures on random graphs for which the strong convergence law holds. (shrink)

In this article, we develop and clarify some of the basic combinatorial properties of the new notion of n-dependence recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, n-dependence corresponds to the inability to encode a random -partite -hypergraph with a definable edge relation. We characterize n-dependence by counting φ-types over finite sets, and in terms of the collapse (...) of random ordered -hypergraph indiscernibles down to order-indiscernibles. (shrink)

A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups or connectivity, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The basic (...) idea underlying the results and examples presented here is that it is possible to construct a countable first-order theory T such that every model of T has a very rich automorphism group, but every finite subset T′ of T has a model which is rigid. (shrink)

The study of random graphs was begun in the 1960s and now has a comprehensive literature. This excellent book by one of the top researchers in the field now joins the study of random graphs (and other random discrete objects) with mathematical logic. The methodologies involve probability, discrete structures and logic, with an emphasis on discrete structures.

We study classes of right-angled Coxeter groups with respect to the strong submodel relation of a parabolic subgroup. We show that the class of all right-angled Coxeter groups is not smooth and establish some general combinatorial criteria for such classes to be abstract elementary classes (AECs), for them to be finitary, and for them to be tame. We further prove two combinatorial conditions ensuring the strong rigidity of a right-angled Coxeter group of arbitrary rank. The combination of these results translates (...) into a machinery to build concrete examples of AECs satisfying given model-theoretic properties. We exhibit the power of our method by constructing three concrete examples of finitary classes. We show that the first and third classes are nonhomogeneous and that the last two are tame, uncountably categorical, and axiomatizable by a single Lω1,ω-sentence. We also observe that the isomorphism relation of any countable complete first-order theory is κ-Borel reducible (in the sense of generalized descriptive set theory) to the isomorphism relation of the theory of right-angled Coxeter groups whose Coxeter graph is an infinite random graph. (shrink)

Networks in nature possess a remarkable amount of structure. Via a series of data‐driven discoveries, the cutting edge of network science has recently progressed from positing that the random graphs of mathematical graph theory might accurately describe real networks to the current viewpoint that networks in nature are highly complex and structured entities. The identification of high order structures in networks unveils insights into their functional organization. Recently, Clauset, Moore, and Newman,1 introduced a new algorithm that identifies (...) such heterogeneities in complex networks by utilizing the hierarchy that necessarily organizes the many levels of structure. Here, we anchor their algorithm in a general community detection framework and discuss the future of community detection. BioEssays 30:934–938, 2008. © 2008 Wiley Periodicals, Inc. (shrink)

§1. Introduction. In this report we wish to describe recent work on a class of first order theories first introduced by Shelah in [32], the simple theories. Major progress was made in the first author's doctoral thesis [17]. We will give a survey of this, as well as further works by the authors and others.The class of simple theories includes stable theories, but also many more, such as the theory of the random graph. Moreover, many of the (...) theories of particular algebraic structures which have been studied recently turn out to be simple. The interest is basically that a large amount of the machinery of stability theory, invented by Shelah, is valid in the broader class of simple theories. Stable theories will be defined formally in the next section. An exhaustive study of them is carried out in [33]. Without trying to read Shelah's mind, we feel comfortable in saying that the importance of stability for Shelah lay partly in the fact that an unstable theory T has 2λ many models in any cardinal λ ≥ ω1 + |T|. (shrink)

Network analysis views complex systems as networks with well-defined structural properties that account for their complexity. These characteristics, which include scale-free behavior, small worlds and communities, are not to be found in networks such as random graphs and lattices that do not correspond to complex systems. They provide therefore a robust ground for claiming the existence of “complex networks” as a non-trivial subset of networks. The theory of complex networks has thus been successful in making systematically explicit relevant (...) marks of complexity in the form of structural properties, and this success is at the root of its current popularity. Much less systematic has been, on the other hand, the definition of the properties of the building components of complex networks. The obvious assumption is that these components must be nodes and links. Generally, however, the internal structure of nodes is not taken into account, and links are serendipitously identified by the perspective with which one looks at the network to be analyzed. For instance, if the nodes are Web pages that contain information about scientific papers, one point of view will match the relevant links with hyperlinks to similar Web pages, and another with citations of other articles. We intend to contribute here a systematic approach to the identification of the components of a complex network that is based on information theory. The approach hinges on some recent results arising from the convergence between the theory of complex networks and probabilistic techniques for content mining. At its core there is the idea that nodes in a complex network correspond to basic information units from which links are extracted via methods of machine learning. Hence the links themselves are viewed as emergent properties, similarly to the broader structural properties mentioned above. Indeed, beside rounding up the theory, this approach based on learning has clear practical benefits, in that it makes networks emerge from arbitrary information domains. We provide examples and applications in a variety of contexts, starting from an information-theoretic reconstruction of the well-known distinction between “strong links” and “weak links” and then delving into specific applications such as business process management and analysis of policy making. (shrink)

The double empathy problem theory posits that autistic social difficulties emerge from an interpersonal misalignment in social experiences and expectations between autistic and non-autistic people. Supporting this, emerging research reveals better social outcomes in interactions within than across neurotypes among autistic and non-autistic people, emphasizing the need to examine the role of the interpersonal context in autistic social outcomes. However, research on peer relationships among autistic youth primarily focuses on individual characteristics in isolation from the interpersonal context. To address (...) this, this preliminary study explored the effects of student-peer neurotype match on peer relationships among autistic and non-autistic youth in an integrated educational setting. We plotted the peer relationship networks among youth in a school club based on systematic observations of peer interactions over eight 45-min sessions. Descriptive network statistics showed that both autistic and non-autistic youth had more and stronger peer relationships with their same- than cross-neurotype peers. Assortativity coefficients revealed a tendency for youth to connect with peers of the same neurotype, rather than with peers with similar social popularity or activity. We further modeled the effects of student-peer neurotype match on peer relationships using exponential random graph models. The findings suggested that student-peer neurotype match predicted the total strength of peer relationships above and beyond the effects of student neurotype, individual heterogeneity in social popularity and activity, and the tendency of mutuality in social relationships. We discussed the strengths and limitations of this study and the implications for future research and inclusion practice. (shrink)

The mathematical field of graph theory has recently been used to provide counterexamples to the Principle of the Identity of Indiscernibles. In response to this, it has been argued that appeal to relations between graphs allows the Principle to survive the counterexamples. In this paper, I aim to show why that proposal does not succeed.

Micro-expressions can reflect an individual’s subjective emotions and true mental state, and they are widely used in the fields of mental health, justice, law enforcement, intelligence, and security. However, one of the major challenges of working with MEs is that their neural mechanism is not entirely understood. To the best of our knowledge, the present study is the first to use electroencephalography to investigate the reorganizations of functional brain networks involved in MEs. We aimed to reveal the underlying neural mechanisms (...) that can provide electrophysiological indicators for ME recognition. A real-time supervision and emotional expression suppression experimental paradigm was designed to collect video and EEG data of MEs and no expressions of 70 participants expressing positive emotions. Based on the graph theory, we analyzed the efficiency of functional brain network at the scalp level on both macro and micro scales. The results revealed that in the presence of MEs compared with NEs, the participants exhibited higher global efficiency and nodal efficiency in the frontal, occipital, and temporal regions. Additionally, using the random forest algorithm to select a subset of functional connectivity features as input, the support vector machine classifier achieved a classification accuracy for MEs and NEs of 0.81, with an area under the curve of 0.85. This finding demonstrates the possibility of using EEG to recognize MEs, with a wide range of application scenarios, such as persons wearing face masks or patients with expression disorders. (shrink)

The critical node detection problem is a central task in computational graph theory due to its large applicability, consisting in deleting $k$ nodes to minimize a certain graph measure. In this article, we propose a new Extremal Optimization-based approach, the Pseudo-Deterministic Noisy Extremal Optimization (PDNEO) algorithm, to solve the Critical Node Detection variant in which the pairwise connectivity is minimized. PDNEO uses an adaptive pseudo-deterministic parameter to switch between random nodes and articulation points during the search, (...) as well as other features, such as noise induction to preserve diversity, greedy search to better exploit the search space and a greater search space exploration mechanism. Numerical experiments on synthetic and real-world networks show the effectiveness of the proposed algorithm compared with existing methods. (shrink)

Graph theory is a specific concept that has numerous applications throughout many industries. Despite the advancement of this technique, graph theory can still yield ambiguous and imprecise results. In order to cut down on these indeterminate factors, neutrosophic logic has emerged as an applicable solution that is gaining significant attention in solving many real-life decision-making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistency, and indeterminacy. However, empirical research on this specific graph set is lacking. Neutrosophic (...) Graph Theory and Algorithms is a collection of innovative research on the methods and applications of neutrosophic sets and logic within various fields including systems analysis, economics, and transportation. While highlighting topics including linear programming, decision-making methods, and homomorphism, this book is ideally designed for programmers, researchers, data scientists, mathematicians, designers, educators, researchers, academicians, and students seeking current research on the various methods and applications of graph theory. (shrink)

Possibly the most fundamental scientific problem is the origin of time and causality. The inherent difficulty is that all scientific theories of origins and evolution consider the existence of time and causality as given. We tackle this problem by starting from the concept of self-organization, which is seen as the spontaneous emergence of order out of primordial chaos. Self-organization can be explained by the selective retention of invariant or consistent variations, implying a breaking of the initial symmetry exhibited by randomness. (...) In the case of time, we start from a random graph connecting primitive “events”. Selection on the basis of consistency eliminates cyclic parts of the graph, so that transitive closure can transform it into a partial order relation of precedence. Causality is assumed to be carried by causal “agents” which undergo a more traditional variation and selection, giving rise to causal laws that are partly contingent, partly necessary. (shrink)

Friendship establishment was analyzed using constructs from social cognitive theory and social network theory. In further studies, we investigated the effect of personality traits, interpersonal self-efficacy, and network structure on the establishment of friendships. In this study, we used social network analysis method and exponential random graph model. The following findings are reported. First, the friendship network of college students had small group characteristics, and the formation of this small group was more based on personality complementarity (...) than similarity. The homogeneity hypothesis of personality was not tenable. Secondly, individuals with dominance or influence personality traits and high interpersonal self-efficacy were more likely to be in the center of the friendship network. Furthermore, personality traits and interpersonal self-efficacy may have interactive effects on the formation of friendship networks. Popularity and activity effects existed in friendship networks, but the reciprocal relationship based on personality traits was not verified. The balance structure can easily explain the agglomeration of friendships in a small range, indicating that small groups of friendships prefer a two-way circular close relationship. Finally, the formation of a friendship network includes the comprehensive process of individual characteristics and endogenous tie formation, which helps us to understand the social population structure and its process over a wider range. (shrink)

Social network theory is an important paradigm of social structure research, which has been widely used in various fields of research. This paper reviews the development process and the latest progress of social network theory research and analyzes the research application of social network. In order to reveal the deep social structure, this paper analyzes the structure of social networks from three levels: microlevel, mesolevel, and macrolevel and reveals the origin, development, perfection, and latest achievements of complex network (...) models. The regular graph model, P1 model, P2 model, exponential random graph model, small-world network model, and scale-free network model are introduced. In the end, the research on the social network structure is reviewed, and social support network and social discussion network are introduced, which are two important contents of social network research. At present, the research on social networks has been widely used in coauthor networks, citation networks, mobile social networks, enterprise knowledge management, and individual happiness, but there are few research studies on multilevel structure, dynamic research, complex network research, whole network research, and discussion network research. This provides space for future research on social networks. (shrink)

We prove that the conjugacy problem for the automorphism group of the random graph is Borel complete, and discuss the analogous problem for some other countably categorical structures.

We show that under Martin's Axiom, the cofinality cf(Aut(Γ)) of the automorphism group of the random graph Γ is 2 ω.

How does international financial aid affect the cooperative behavior of local non-governmental organizations (NGOs)? Can NGOs, while turning global, preserve peer connections with local actors and be engaged in local issues? The civil society literature contains competing perspectives on and reports of how international financial aid may restructure local civic networks. Some scholars argue that international support comes at the expense of local integration as inclusion in global networks takes local NGOs out of the local context, while others find evidence (...) that organizations do not have to face “a forced choice”, and may well be integrated both globally and locally. Drawing on this scholarship, we examine two hypotheses on how transnational funding influences cooperation patterns among NGOs. The hierarchy argument states that public entities tend to cooperate with internationally funded NGOs as external contact signals quality and trustworthiness. The segregation argument, on the contrary, suggests financial homophily according to which organizations are more likely to choose peers similar in sources of funding. To test these hypotheses, we apply Exponential Random Graph Models to the data on cooperation among 221 Kazakhstani NGOs. Results support the segregation hypothesis implying that NGOs are likely to have a bias towards similarly funded peers. (shrink)

Let L ω ∞ω be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n -1 satisfies certain simple conditions on its growth rate, then for every σ∈ L ω ∞ω , the probability that σ holds (...) for the random graph on n vertices converges. In fact, if $p(n) = n^{-\alpha}, \alpha > 1$ , then the probability is either smaller than 2 -n d for some $d > 0$ , or it is asymptotic to cn -d for some $c > 0, d \geq 0$ . Results on the difficulty of computing the asymptotic probability are given. (shrink)

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

Assuming CH, let be the saturated random graph of cardinality ω1. In this paper we prove that it is consistent that and can be any two prescribed regular cardinals subject only to the requirement.

Libertarians claim that human behaviour is undetermined and cannot be predicted from knowledge of past history even in principle since it is based on the random movements of quantum mechanics. Determinists on the other hand deny thatmacroscopic phenomena can be activated bysub-microscopic events, and assert that if human action is unpredictable in the way claimed by libertarians, it must be aimless and irrational. This is not true of some types of random behaviour described in this paper. Random (...) behaviour may make one unpredictable to opponents and may therefore be rational. Similarly, playing a game with a mixed strategy may have an unpredictable outcome in every single play, but the strategy is rational, in that it is meant to maximize the expected value of an objective, be it private or social. As to whether the outcome of such behaviour is genuinely unpredictable as in quantum mechanics, or predictable by a hypothetical outside observer knowing all natural laws, it is argued that it makes no difference in practice, as long as it is not humanly predictable. Thus we have a new version of libertarianism which is compatible with determinism. (shrink)

Studies to neutrosophic graphs happens to be not only innovative and interesting, but gives a new dimension to graph theory. The classic coloring of edge problem happens to give various results. Neutrosophic tree will certainly find lots of applications in data mining when certain levels of indeterminacy is involved in the problem. Several open problems are suggested.

This book covers a wide variety of topics in combinatorics and graph theory.

We consider random processes more general than those considered by Erdös and Rényi for generating the countable random graph. It is proved that, in the category sense, almost all random processes we consider generate the countable random graph with probability 1. Under a weak boundedness assumption we give a criterion for the random processes which generate the countable random graph almost surely. We also consider further questions asked by Jackson regarding the (...) outcome graphs when the process fails to produce the countable random graph. (shrink)

Given a countable graph, we say a set A of its vertices is universal if it contains every countable graph as an induced subgraph, and A is weakly universal if it contains every finite graph as an induced subgraph. We show that, for almost every graph on, (1) every set of positive upper density is universal, and (2) every set with divergent reciprocal sums is weakly universal. We show that the second result is sharp (i.e., a (...) random graph on will almost surely contain non‐universal sets with divergent reciprocal sums) and, more generally, that neither of these two results holds for a large class of partition regular families. (shrink)