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).

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 show that under Martin's Axiom, the cofinality cf(Aut(Γ)) of the automorphism group of the random graph Γ is 2 ω.

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.

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.

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)

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)

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.

Let $\Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $\Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $\operatorname {Aut}(\Gamma)^{\ast}$ , where $\operatorname {Aut}(\Gamma)^{\ast}$ is the group of all isomorphisms and anti-isomorphisms of $\Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nešetřil and Rödl (...) and a strong finite submodel property for $\Gamma$. (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 define an evolving Shelah‐Spencer process as one by which a random graph grows, with at each time a new node incorporated and attached to each previous node with probability, where is fixed. We analyse the graphs that result from this process, including the infinite limit, in comparison to Shelah‐Spencer sparse random graphs discussed in [21] and throughout the model‐theoretic literature. The first order axiomatisation for classical Shelah‐Spencer graphs comprises a Generic Extension axiom scheme and a No (...) Dense Subgraphs axiom scheme. We show that in our context Generic Extension continues to hold. While No Dense Subgraphs fails, a weaker Few Rigid Subgraphs property holds. (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)

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not (...) model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures (...) and Algorithms 26 119–145] of D)=log1/pn+O. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures (...) and Algorithms 26 119–145] of D)=log1/pn+O. (shrink)

We study the cardinal invariants of measure and category after adding one random real. In particular, we show that the number of measure zero subsets of the plane which are necessary to cover graphs of all continuous functions may be large while the covering for measure is small.

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.

The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique countably saturated linear order of cardinality \. We provide some examples of pairwise non-isomorphic countably saturated linear orders of cardinality \, under different set-theoretic assumptions. We give a new proof of the old theorem of Harzheim, that the class of countably saturated linear orders has a uniquely determined one-element basis. From (...) our proof it follows that this minimal linear order is a Fraïssé limit of certain Fraïssé class. In particular, it is homogeneous with respect to countable subsets. Next we prove the existence and uniqueness of the uncountable version of the random graph. This graph is isomorphic to \,\in \cup \ni )\), where \\) is the set of hereditarily countable sets, and two sets are connected if one of them is an element of the other. In the last section, an example of a prime countably saturated Boolean algebra is presented. (shrink)

A large number of cross-references to various bodies of text are used in legal texts, each serving a different purpose. It is often necessary for authorities and companies to look into certain types of these citations. Yet, there is a lack of automatic tools to aid in this process. Recently, citation graphs have been used to improve the intelligibility of complex rule frameworks. We propose an algorithm that builds the citation graph from a document and automatically labels each edge (...) according to its purpose. Our method uses the citing text only and thus works only on citations who’s purpose can be uniquely identified by their surrounding text. This framework is then applied to the US code. This paper includes defining and evaluating a standard gold set of labels that cover a vast majority of citation types which appear in the “US Code” but are still short enough for practical use. We also proposed a novel linear-chain conditional random field model that extracts the features required for labeling the citations from the surrounding text. We then analyzed the effectiveness of different clustering methods such as K-means and support vector machine to automatically label each citation with the corresponding label. Besides this, we talk about the practical difficulties of this task and give a comparison of human accuracy compared to our end-to-end algorithm. (shrink)

Background and objectivesThe study of brain functional connectivity alterations in children with Attention-Deficit/Hyperactivity Disorder has been the subject of considerable investigation, but the biological mechanisms underlying these changes remain poorly understood. Here, we aim to investigate the brain alterations in patients with ADHD and Typical Development children and accurately classify ADHD children from TD controls using the graph-theoretical measures obtained from resting-state fMRI.Materials and methodsWe investigated the performances of rs-fMRI data for classifying drug-naive children with ADHD from TD controls. (...) Fifty six drug-naive ADHD children and 56 age matched TD controls were included in this study. The graph measures extracted from rs-fMRI functional connectivity were used as features. Extracted network-based features were fed to the RFE feature selection algorithm to select the most discriminating subset of features. We trained and tested Support Vector Machine, Random Forest, and Gradient Boosting using Peking center data from ADHD-200 database to classify ADHD and TD children using discriminative features. In addition to the machine learning approach, the statistical analysis was conducted on graph measures to discover the differences in the brain network of patients with ADHD.ResultsAn accuracy of 78.2% was achieved for classifying drug-naive children with ADHD from TD controls employing the optimal features and the GB classifier. We also performed a hub node analysis and found that the number of hubs in TD controls and ADHD children were 8 and 5, respectively, indicating that children with ADHD have disturbance of critical communication regions in their brain network. The findings of this study provide insight into the neurophysiological mechanisms underlying ADHD.ConclusionPattern recognition and graph measures of the brain networks, based on the rs-fMRI data, can efficiently assist in the classification of ADHD children from TD controls. (shrink)

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)

Recent advances in neuroscience indicate that analysis of bio-signals such as rest state electroencephalogram and eye-tracking data can provide more reliable evaluation of children autism spectrum disorder than traditional methods of behavior measurement relying on scales do. However, the effectiveness of the new approaches still lags behind the increasing requirement in clinical or educational practices as the “bio-marker” information carried by the bio-signal of a single-modality is likely insufficient or distorted. This study proposes an approach to joint analysis of EEG (...) and eye-tracking for children ASD evaluation. The approach focuses on deep fusion of the features in two modalities as no explicit correlations between the original bio-signals are available, which also limits the performance of existing methods along this direction. First, the synchronization measures, information entropy, and time-frequency features of the multi-channel EEG are derived. Then a random forest applies to the eye-tracking recordings of the same subjects to single out the most significant features. A graph convolutional network model then naturally fuses the two group of features to differentiate the children with ASD from the typically developed subjects. Experiments have been carried out on the two types of the bio-signals collected from 42 children. The results indicate that the proposed approach can achieve an accuracy of 95% in ASD detection, and strong correlations exist between the two bio-signals collected even asynchronously, in particular the EEG synchronization against the face related/joint attentions in terms of covariance. (shrink)

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.

An illustrated exploration of fandom that combines academic essays with artist pages and experimental texts. Fandom as Methodology examines fandom as a set of practices for approaching and writing about art. The collection includes experimental texts, autobiography, fiction, and new academic perspectives on fandom in and as art. Key to the idea of “fandom as methodology” is a focus on the potential for fandom in art to create oppositional spaces, communities, and practices, particularly from queer perspectives, but also through transnational, (...) feminist and artist-of-color fandoms. The book provides a range of examples of artists and writers working in this vein, as well as academic essays that explore the ways in which fandom can be theorized as a methodology for art practice and art history. Fandom as Methodology proposes that many artists and art writers already draw on affective strategies found in fandom. With the current focus in many areas of art history, art writing, and performance studies around affective engagement with artworks and imaginative potentials, fandom is a key methodology that has yet to be explored. Interwoven into the academic essays are lavishly designed artist pages in which artists offer an introduction to their use of fandom as methodology. Contributors Taylor J. Acosta, Catherine Grant, Dominic Johnson, Kate Random Love, Maud Lavin, Owen G. Parry, Alice Butler, SooJin Lee, Jenny Lin, Judy Batalion, Ika Willis. Artists featured in the artist pages Jeremy Deller, Ego Ahaiwe Sowinski, Anna Bunting-Branch, Maria Fusco, Cathy Lomax, Kamau Amu Patton, Holly Pester, Dawn Mellor, Michelle Williams Gamaker, The Women of Colour Index Reading Group, Liv Wynter, Zhiyuan Yang. (shrink)

Exponential random graph modeling (ERGM) is used here to test hypotheses derived from human behavioral ecology about the adaptive nature of human food sharing. Respondents in all (n = 317) households in the fishing and sea-hunting village of Lamalera, Indonesia, were asked to name those households to whom they had more frequently given (and from whom they had more frequently received) food during the preceding sea-hunting season. The responses were used to construct a social network of between-household food-sharing (...) relationships in the village. The results show that kinship, proximity, and reciprocal sharing all strongly increase the probability of giving food to a household. The effects of kinship and distance are relatively independent of each other, although reciprocity is more common among residentially and genealogically close households. The results show support for reciprocal altruism as a motivation for food sharing, while kinship and distance appear to be important partner-choice criteria. (shrink)

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the natural uniformity on (...) it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (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)

We prove, by a probabilistic argument, that a class of ω-categorical structures, on which algebraic closure defines a pregeometry, has the finite submodel property. This class includes any expansion of a pure set or of a vector space, projective space or affine space over a finite field such that the new relations are sufficiently independent of each other and over the original structure. In particular, the random graph belongs to this class, since it is a sufficiently independent expansion (...) of an infinite set, with no structure. The class also contains structures for which the pregeometry given by algebraic closure is non-trivial. (shrink)

We show that for finite n⩾3n⩾3, every first-order axiomatisation of the varieties of representable n-dimensional cylindric algebras, diagonal-free cylindric algebras, polyadic algebras, and polyadic equality algebras contains an infinite number of non-canonical formulas. We also show that the class of structures for each of these varieties is non-elementary. The proofs employ algebras derived from random graphs.

In the context of solving large distributed constraint optimization problems, belief-propagation and incomplete inference algorithms are candidates of choice. However, in general, when the problem structure is very cyclic, these solution methods suffer from bad performance, due to non-convergence and many exchanged messages. As to improve performances of the MaxSum inference algorithm when solving cyclic constraint optimization problems, we propose here to take inspiration from the belief-propagation-guided decimation used to solve sparse random graphs. We propose the novel DeciMaxSum method, (...) which is parameterized in terms of policies to decide when to trigger decimation, which variables to decimate and which values to assign to decimated variables. Based on an empirical evaluation on a classical constraint optimization benchmarks, some of these combinations of policies, using periodic decimation, cycle detection-based decimation, parallel and non parallel decimation, random or deterministic variable selection and deterministic or random sampling for value selection, outperform state-of-the-art competitors in many settings. (shrink)

Organizational networks are a widely used approach to deal with the “wicked problems” of disasters. However, current studies are insufficient in examining what strategies organizations actually employ to select partners in a complex environment of disaster, particularly in the centralized administrative context. This case study uses exponential random graph models to explore different partnering strategies that organizations used to form organizational networks in response to the Tianjin Port blast, a well-known disaster in China. Results demonstrate that participating organizations (...) prefer the bonding structure strategy to form “reciprocity” and “transitive clustering,” the power concentration strategy to work with popular organizations, and the homophily strategy to work with similar attribute organizations. However, contextual backgrounds influenced organizational attributes and strategies. This study discusses the implications of the findings and offers recommendations for enhancing collaboration among organizations. (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)

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)

With the increasing attention to climate change, air pollution, and related public health issues, China’s new energy vehicles industry has developed rapidly. However, few studies investigated the evolution of interorganizational collaborative innovation networks in the sector domain of NEVs and the influence of different drivers on the establishment of innovation relationships. In this context, this paper uses the joint invention patent of Shenzhen, a low-carbon pilot city of China, to investigate the dynamics of network influencing factors. The social network analysis (...) shows that the scale of coinvention network of NEVs is constantly increasing, which is featured with diversified cooperative entities, and collaboration depth is also expanding. The empirical results from the Exponential Random Graph Model demonstrate that, with the deepening of collaborative innovation, technological upgrading caused by knowledge exchange makes organizations in the network more inclined to cognitive proximity and less dependent on geographical proximity. In addition, organizational proximity and triadic closure contribute positively to the collaborative network, with their relevance remaining nearly the same, while the impeding effect of cultural/language difference is slightly decreasing with time. (shrink)

Assuming certain conditions on a class equation image of finitely generated first-order structures admitting the model-theoretical construction of a Fraïssé limit, we characterize retracts of such limits as algebraically closed structures in a class naturally related to equation image. In this way we generalize an earlier description of retracts of the countably infinite random graph.