Directed Sets and Malitz-Cauchy-Completions

This is a study of the set of the Malitz-completions (which are a special case of Cauchy-completions) of a given infinite first-order structure, put in relation with properties of directed sets.     

The phase transition of the directed polymer on disordered hierarchical lattices

The directed polymer on disordered hierarchical lattices is studied using an exact renormalization scheme. The phase transition is studied and a hyperscaling relation is derived. The fixed distributions of the renormalized energies are obtained numerically. The specific heat and associated exponents are computed from the fixed distributions.     

Applications of the Wold decomposition to the study of row contractions associated with directed graphs

Based on a Wold decomposition for families of partial isometries and projections of Cuntz-Krieger-Toeplitz-type, we extend several fundamental theorems from the case of single vertex graphs to the general case of countable directed graphs with no sinks. We prove a Szego-type factorization theorem for CKT families, which leads to information on the structure of the unit ball in free semigroupoid algebras, and show that joint similarity implies joint unitary equivalence for such families. For each graph we prove a generalization of von Neumann's inequality which applies to row contractions of operators on Hilbert space which are related to the graph in a natural way. This yields a functional calculus determined by quiver algebras and free semigroupoid algebras. We establish a generalization of Coburn's theorem for the -algebra of a CKT family, and prove a universality theorem for -algebras generated by these families. In both cases, the -algebras generated by quiver algebras play the universal role.

     

-Decompositions of and D v ∪P where P is a 2-Regular Subgraph of D v

In this paper, we extend the study of C₄-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D_v, then and D_v∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.     

Continuous opinion model in small-world directed networks

In the compromise model of continuous opinions proposed by Deffuant et al., the states of two agents in a network can start to converge if they are neighbors and if their opinions are sufficiently close to each other, below a given threshold of tolerance ?. In directed networks, if agent i is a neighbor of agent j,j need not be a neighbor of i. In Watts-Strogatz networks we performed simulations to find the averaged number of final opinions 〈F〉 and their distribution as a function of ? and of the network structural disorder. In directed networks 〈F〉 exhibits a rich structure, being larger than in undirected networks for higher values of ?, and smaller for lower values of ?.     

Implementing minimal clock skew Directed Logic

Although the physics of computing allows the possibility of logic operations with no energy dissipation, over 40 years of work by brilliant scientists in many fields has not achieved it. The solution described here required breaking from the tacit assumptions that logic gates had to be electronic. The system is implemented entirely with passive optical components. Also needed was a logic that could utilize those passive components. Hardy and Shamir showed how to map a Boolean logic problem into a form suitable to be implemented by light flowing through various paths and cascaded as needed. This paper examines a modular approach to implementing their approach (called Directed Logic) in an integrated optical system. We start from unit cells, implementing a dynamic flip-flop principle and combine the cells in a network or “logic fabric.” Contrary to proofs by the founders of this field, speed is limited only by the message bandwidth of the optical signal, and, of course, no energy is dissipated. There are still aspects that need additional work on issues like accuracy using analog components and size relative to electronics. But the basic problem is solved at last and paths toward solving the remaining problems have been identified.     

Inducibility of directed paths

A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.     

Stationary directed polymers and energy solutions of the Burgers equation

We consider the stationary O’Connell–Yor model of semi-discrete directed polymers in a Brownian environment in the intermediate disorder regime and show convergence of the increments of the log-partition function to the energy solutions of the stochastic Burgers equation.The proof does not rely on the Cole–Hopf transform and avoids the use of spectral gap estimates for the discrete model. The key technical argument is a second-order Boltzmann–Gibbs principle.     

Representing Sparse Gaussian DAGs as Sparse R-Vines Allowing for Non-Gaussian Dependence

Modeling dependence in high-dimensional systems has become an increasingly important topic. Most approaches rely on the assumption of a multivariate Gaussian distribution such as statistical models on directed acyclic graphs (DAGs). They are based on modeling conditional independencies and are scalable to high dimensions. In contrast, vine copula models accommodate more elaborate features like tail dependence and asymmetry, as well as independent modeling of the marginals. This flexibility comes however at the cost of exponentially increasing complexity for model selection and estimation. We show a novel connection between DAGs with limited number of parents and truncated vine copulas under sufficient conditions. This motivates a more general procedure exploiting the fast model selection and estimation of sparse DAGs while allowing for non-Gaussian dependence using vine copulas. By numerical examples in hundreds of dimensions, we demonstrate that our approach outperforms the standard method for vine structure selection. Supplementary material for this article is available online.     

Sums and differences along Hamiltonian cycles

Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How do the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest.