All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 37 Next

Displaying 721 – 740 of 5365

Showing per page

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

Asymptotic spectral analysis of generalized Erdős-Rényi random graphs

Song Liang, Nobuaki Obata, Shuji Takahashi (2007)

Banach Center Publications

Motivated by the Watts-Strogatz model for a complex network, we introduce a generalization of the Erdős-Rényi random graph. We derive a combinatorial formula for the moment sequence of its spectral distribution in the sparse limit.

Asymptotic spectral analysis of growing graphs: odd graphs and spidernets

Daisuke Igarashi, Nobuaki Obata (2006)

Banach Center Publications

Two new examples are given for illustrating the method of quantum decomposition in the asymptotic spectral analysis for a growing family of graphs. The odd graphs form a growing family of distance-regular graphs and the two-sided Rayleigh distribution appears in the limit of vacuum spectral distribution of the adjacency matrix. For a spidernet as well as for a growing family of spidernets the vacuum distribution of the adjacency matrix is the free Meixner law. These distributions are calculated...

Asymptotic spectral distributions of distance-k graphs of Cartesian product graphs

Yuji Hibino, Hun Hee Lee, Nobuaki Obata (2013)

Colloquium Mathematicae

Let G be a finite connected graph on two or more vertices, and G [ N , k ] the distance-k graph of the N-fold Cartesian power of G. For a fixed k ≥ 1, we obtain explicitly the large N limit of the spectral distribution (the eigenvalue distribution of the adjacency matrix) of G [ N , k ] . The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.

Atomic compactness for reflexive graphs

Christian Delhommé (1999)

Fundamenta Mathematicae

A first order structure with universe M is atomic compact if every system of atomic formulas with parameters in M is satisfiable in provided each of its finite subsystems is. We consider atomic compactness for the class of reflexive (symmetric) graphs. In particular, we investigate the extent to which “sparse” graphs (i.e. graphs with “few” vertices of “high” degree) are compact with respect to systems of atomic formulas with “few” unknowns, on the one hand, and are pure restrictions of their...

Atoms and partial orders of infinite languages

Werner Kuich, N. W. Sauer (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under ⊆ . This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

Atoms and partial orders of infinite languages

Werner Kuich, N. W. Sauer (2010)

RAIRO - Theoretical Informatics and Applications

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under ⊆. This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

Automata-based representations for infinite graphs

Salvatore La Torre, Margherita Napoli (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...

Currently displaying 721 – 740 of 5365