The cover time of random geometric graphs

We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r. Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x. The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G. Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011     

Quartets in maximal weakly compatible split systems

Weakly compatible split systems are a generalization of unrooted evolutionary trees and are commonly used to display reticulate evolution or ambiguity in biological data. They are collections of bipartitions of a finite set X of taxa (e.g. species) with the property that, for every four taxa, at least one of the three bipartitions into two pairs (quartets) is not induced by any of the X-splits. We characterize all split systems where exactly two quartets from every quadruple are induced by some split. On the other hand, we construct maximal weakly compatible split systems where the number of induced quartets per quadruple tends to 0 with the number of taxa going to infinity.     

判别分析法对增发股投资价值的分析及预测

本文通过增发股相关指标数据的特别处理 ,对增发股投资价值进行了判别分析 ,求得了判别函数 ,并应用于增发股的投资预测     

城市再生水BOT项目特许经营权竞标机制设计

本文研究了城市再生水BOT项目特许经营权竞标机制设计问题.运用激励机制设计思想建立了满足个体理性和激励相容约束的拍卖模型,并通过求解此模型得到了最优的拍卖机制.最优拍卖机制不仅能诱导企业真实地披露自己的成本类型,还能提高政府对社会资源的配置效率.     

基于Ito方程的广告效应理论预测模型

广告效应取决于许多因素,假设在t时刻广告效应是t以及在t时刻的接收率S(t)的函数,利用Ito方程,作为连续型随机变量,从理论上给出了一种广告效应的预测模型,包括广告的即时效应、延续效应、累计效应及扩散效应模型.     

Logarithmic reduction of the level of randomness in some probabilistic geometric constructions

Many of the surprising phenomena occurring in high dimensions are proved by use of probabilistic arguments, which show the existence of organized and regular structures but do not hint as to where exactly do these structures lie. It is an intriguing question whether some of them could be realized explicitly. In this paper we show that the amount of randomness used can be reduced significantly in many of these questions from asymptotic convex geometry, and most of the random steps can be substituted by completely explicit algorithmic steps. The main tool we use is random walks on expander graphs.     

Relationships between combinatorial measurements and Orlicz norms

We establish in a setting of harmonic analysis precise relationships between combinatorial measurements and Orlicz norms. These relationships further extend and sharpen prior results concerning extensions of the Littlewood 2n/(n+1)-inequalities, the n-dimensional Khintchin inequalities, and the Kahane-Khintchin inequality.     

Distance-two labellings of Hamming graphs

Let j≥k≥0 be integers. An ?-L(j,k)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…,?} such that |?(u)−?(v)|≥j if u,v are adjacent and |?(u)−?(v)|≥k if they are distance two apart. Let λ_j,k(G) be the smallest integer ? such that G admits an ?-L(j,k)-labelling. Define to be the smallest ? if G admits an ?-L(j,k)-labelling with ?(V)={0,1,2,…,?} and ∞ otherwise. An ?-cyclic L(j,k)-labelling is a mapping ?:V→Z_? such that |?(u)−?(v)|_?≥j if u,v are adjacent and |?(u)−?(v)|_?≥k if they are distance two apart, where |x|_?=min{x,?−x} for x between 0 and ?. Let σ_j,k(G) be the smallest ?−1 of such a labelling, and define similarly to . We determine λ_2,0, , σ_2,0 and for all Hamming graphs K_q1□K_q2□?□K_qd (d≥2, q₁≥q₂≥?≥q_d≥2) and give optimal labellings, with the only exception being for q≥4. We also prove the following “sandwich theorem”: If q₁ is sufficiently large then for any graph G between K_q1□K_q2 and K_q1□K_q2□?□K_qd, and moreover we give a labelling which is optimal for these eight invariants simultaneously.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).