Strong homotopy induced by adjacency structure

This paper generalizes the concept of SA-homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA-strong deformation retract of a simple graph G could be obtained by removing trivial vertices one by one, which makes it possible to allow an iterative algorithm of finding all SA-strong deformation retracts of G. We also obtain that two simple graphs are SA-homotopy equivalent if and only if they have graph isomorphic cores. Compared with the graph homotopy transformation defined by S.T. Yau et al. and the s-homotopy transformation defined by R. Boulet et al., the main advantage of SA-homotopy transformation is that it could reflect correspondences between vertices, and hence it more accurately describe the transformation process than the graph homotopy transformation and s-homotopy transformation. As an application of SA-homotopy on graphs, we introduce the mapping class group of a graph, which also shows its advantage over the graph homotopy transformation and the s-homotopy transformation.     

Combinatorial structure and adjacency of vertices of polytope of b-factors

In the present paper in terms of the graph theory we describe the structure and vertices adjacency criterion of b-factors polyhedron. The special attention is paid to nonintegral vertices. Results of the present paper, in particular, generalize properties of nonintegral vertices of TSP polyhedron, give vertices adjacency criterion of a transportation polytope.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

Two optimal strategies for active learning of causal models from interventional data

From observational data alone, a causal DAG is only identifiable up to Markov equivalence. Interventional data generally improves identifiability; however, the gain of an intervention strongly depends on the intervention target, that is, the intervened variables. We present active learning (that is, optimal experimental design) strategies calculating optimal interventions for two different learning goals. The first one is a greedy approach using single-vertex interventions that maximizes the number of edges that can be oriented after each intervention. The second one yields in polynomial time a minimum set of targets of arbitrary size that guarantees full identifiability. This second approach proves a conjecture of Eberhardt (2008) [1] indicating the number of unbounded intervention targets which is sufficient and in the worst case necessary for full identifiability. In a simulation study, we compare our two active learning approaches to random interventions and an existing approach, and analyze the influence of estimation errors on the overall performance of active learning.     

Presence or absence of analytic structure in maximal ideal spaces

We study extensions of Wermer’s maximality theorem to several complex variables. We exhibit various smoothly embedded manifolds in complex Euclidean space whose hulls are non-trivial but contain no analytic disks. We answer a question posed by Lee Stout concerning the existence of analytic structure for a uniform algebra whose maximal ideal space is a manifold.     

On an adjacency property of graphs

A graph G has property A(m, n, k) if for any sequence of m + n distinct points of G, there are at least k other points, each of which is adjacent to the first m points of the sequence but not adjacent to any of the latter n points. the minimum order among all graphs with property A(m, n, k) is denoted a(m, n, k). Bounds are given on the numbers a(m, n, k) and some exact results are indicated.     

Banach manifold structure and infinite-dimensional analysis for causal fermion systems

Annals of Global Analysis and Geometry - A mathematical framework is developed for the analysis of causal fermion systems in the infinite-dimensional setting. It is shown that the regular spacetime...     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

Discrete operator fields as carriers of causal spacetime structure. Internal symmetry

Scientific Council on the Problem Complex Kibernetika, USSR Academy of Sciences. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 84, No. 3, pp. 339–352, September, 1990.     

The adjacency graphs of some feedback shift registers

In this paper, we consider the adjacency graphs of some feedback shift registers (FSRs), namely, the FSRs with characteristic functions of the form \(g=(x_0+x_1)*f\). Firstly, we give some properties about these FSRs. We prove that these FSRs generate only prime cycles, and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. For example, it is shown that, when f contains an odd number of terms, the adjacency graph of \({\mathrm {FSR}}((x_0+x_1)*f)\) can be determined directly from the adjacency graph of \({\mathrm {FSR}}(f)\). Then, as an application of these results, we continue the work of Li et al. (IEEE Trans Inf Theory 60(5):3052–3061, 2014) to determine the adjacency graphs of \({\mathrm {FSR}}((1+x)^4p(x))\) and \({\mathrm {FSR}}((1+x)^5p(x))\), where p(x) is a primitive polynomial, and construct a large class of De Bruijn sequences from them.     

On the adjacency matrix of a threshold graph

A threshold graph on n   vertices is coded by a binary string of length n−1$n-1$. We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases.     

Relationship of causal effects in a causal chain and related inference

This paper discusses the relationship among the total causal effect and local causal effects in a causal chain and identifiability of causal effects. We show a transmission relationship of causal effects in a causal chain. According to the relationship, we give an approach to eliminating confounding bias through controlling for intermediate variables in a causal chain.     

Transformations preserving adjacency and base subsets of spine spaces

Transformations of spine spaces which preserve base subsets preserve also adjacency. They either preserve the two sorts of projective adjacency or interchange them. Lines of a spine space can be defined in terms of adjacency, except one case where projective lines have no proper extensions to projective maximal strong subspaces, and thus adjacency preserving transformations are collineations.     

Identifiability of causal effect for a simple causal model

Counterfactual model is put forward to discuss the causal inference in the directed acyclic graph and its corresponding identifiability is thus studied with the ancillary information based on conditional independence. It is shown that the assumption of ignorability can be expanded to the assumption of replaceability,under which the causal efiects are identifiable.