Band limited functions on quantum graphs

The notion of band limited functions is introduced on a quantum graph. The main results of the paper are a uniqueness theorem and a reconstruction algorithm of such functions from discrete sets of values. It turns out that some of our band limited functions can have compact supports and their frequencies can be localized on the ``time" side. It opens an opportunity to consider signals of a variable band width and to develop a sampling theory with variable rate of sampling.

     

A property of subgroups of infinite index in a free group

We prove that if is a finitely generated subgroup of infinite index in a free group , then, in a certain statistical meaning, the normal subgroup generated by ``randomly' chosen elements of has trivial intersection with .

     

P_n~k和T_((k_1,k_2,…,k_n))的色多项式

本文研究了图Pnk和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及Pn2仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

Lower Bound on de Bruijn Graphs Out-degree for Lower Traffic Load in Peer-to-peer Networks

Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.     

Structural covariance of graphs

Algebraic structures including multiple rank tensors, linear and non-linear operators are related to and represented with various types of graphs. Special emphasis is placed on linear operators e.g. on the Hibert space. A different graph represents the same operator depending on the basis frame used, in general non-orthonormal. All such graphs are shown to belong in one equivalence class and are termed structurally covariant. Crucial indices related to eigenvalues but invariant under any basis frame changes including non-orthonormal ones provide one way to characterize each class. A set of rules are given that allow one to find the graphs structurally covarinat with a given one and/or to deduce the class indices directly by simple pictorial manipulations on a graph. Applications in various fields including the quantum theory of molecules and reactions are indicated.     

Deformational covariance of graphs

Graphs on n vertices are classified into equivalence classes under the linear group L(n). All graphs representing the same operator on a vector space V _n belong to the same class. Graphs of different operators may or may not belong to the same class as ascertained by rules that were given by the author. Graphs in the same class are structurally covariant. If, in addition, two graphs can be continuously deformed into each other in the sense of varying line strengths while remaining structurally covariant throughout, then the two graphs are termed deformationally covariant along such paths. Applications in the quantum theory of chemistry and to the dynamic stability theory of coupled reaction systems which occur in various fields are indicated.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Spectral Sequences on Combinatorial Simplicial Complexes

The goal of this paper is twofold. First, we give an elementary introduction to the usage of spectral sequences in the combinatorial setting. Second we list a number of applications.In the first group of applications the simplicial complex is the nerve of a poset; we consider general posets and lattices, as well as partition-type posets. Our last application is of a different nature: the -quotient of the complex of directed forests is a simplicial complex whose cell structure is defined combinatorially.