What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?

A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well-known conjectures by G. Hajós, P. Erd?s, and P.J. Kelly: (1) [B. Jackson] Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{n}{2} $\end{document} dicycles. (2) [W. Bienia & H. Meyniel] Every eulerian digraph is decomposable into at most n dicycles. Certain observations lead us to make three other conjectures: (a) Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{2n}}{3} $\end{document} dicycles. (b) Every symmetric digraph with n > 1 is decomposable into at most 2n – 3 dicycles. (c) Every eulerian digraph with n > 1 is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{8n}}{3} $\end{document} – 3 dicycles.     

A characterization of stochastically stable networks

Jackson and Watts (J Econ Theory 71: 44–74, 2002) have examined the dynamic formation and stochastic evolution of networks. We provide a refinement of pairwise stability, p-pairwise stability, which allows us to characterize the stochastically stable networks without requiring the “tree construction” and the computation of resistance that may be quite complex. When a -pairwise stable network exists, it is unique and it coincides with the unique stochastically stable network. To solve the inexistence problem of p-pairwise stable networks, we define its set-valued extension with the notion of p-pairwise stable set. The -pairwise stable set exists and is unique. Any stochastically stable networks is included in the -pairwise stable set. Thus, any network outside the -pairwise stable set must be considered as a non-robust network. We also show that the -pairwise stable set can contain no pairwise stable network and we provide examples where a set of networks is more “stable” than a pairwise stable network.     

On the Enumeration and Generation of Nonweight Equivalent Rate 1/2 Convolutional Codes

The weight equivalence of rate $\frac{1}{2} $ binary convolutional codes and the problem of enumeration and generation of all nonweight equivalent codes is considered for a given memory order m. This is done during the generation process by first ordering the encoders into classes such that it becomes easy to recognize the weight equivalence as well as the catastrophic error propagation conditions. Subclasses of respectively self and nonself reciprocal as well as catastrophic and noncatastrophic encoders are introduced. The cardinal number of these classes and subsequently the number of “nonweight equivalent” codes are then computed recursively as a function of m. Finally, since all the relations amount to simple convolutions they are compactly represented by generating functions which are tabulated.     

Improved bounds on equilibria solutions in the network design game

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most \(H_n\), the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most \(H_n \left( 1-\frac{1}{\Theta (n^4)} \right) \), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most \(H_{n/2} + \varepsilon \) for any \(\varepsilon \) starting from some suitable \(n \ge n(\varepsilon )\).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of \(\frac{4}{3}\) and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of \(\frac{4}{3}\), and provide an upper bound of \(\frac{26}{19}\). To the end, we conjecture and argue that the right answer is \(\frac{4}{3}\).     

On Universality of Critical Behavior in the Focusing Nonlinear Schrödinger Equation, Elliptic Umbilic Catastrophe and the Tritronquée Solution to the Painlevé-I Equation

We argue that the critical behavior near the point of “gradient catastrophe” of the solution to the Cauchy problem for the focusing nonlinear Schrödinger equation $i\epsilon \varPsi _{t}+\frac{\epsilon^{2}}{2}\varPsi _{xx}+|\varPsi |^{2}\varPsi =0We argue that the critical behavior near the point of “gradient catastrophe” of the solution to the Cauchy problem for the focusing nonlinear Schr?dinger equation , ε ≪1, with analytic initial data of the form is approximately described by a particular solution to the Painlevé-I equation.      

An Inequality on the Coding Gain of Densest Lattice Packings in Successive Dimensions

A lower bound of the form is derived on the coding gain of the densest n-dimensional (n-D) lattice(s). The bound is obtained based on constructing an n-D lattice which consists of parallel layers. Each layer isselected as a translated version of a densest ( n-1)-D lattice.0The relative positioning of the layers is adjusted to make the coding gainas large as possible. For large values of n, the bound isimproved through tightening Ryskov's inequality on covering radius andminimum distance of a lattice.     

A Multivariate CLT for Bounded Decomposable Random Vectors with the Best Known Rate

We prove a multivariate central limit theorem with explicit error bound in a non-smooth function distance for sums of bounded decomposable \(d\)-dimensional random vectors. The decomposition structure is similar to that of Barbour et al. (J Combin Theory Ser 47:125–145, 1989) and is more general than the local dependence structure considered in Chen and Shao (Ann Probab 32:1985–2028, 2004). The error bound is of the order \(d^{\frac{1}{4}} n^{-\frac{1}{2}}\), where \(d\) is the dimension and \(n\) is the number of summands. The dependence on \(d\), namely \(d^{\frac{1}{4}}\), is the best known dependence even for sums of independent and identically distributed random vectors, and the dependence on \(n\), namely \(n^{-\frac{1}{2}}\), is optimal. We apply our main result to a random graph example.     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Estimation of an important constant in sieve method

ζ _k is one of the most important constant in the sieve methods. This paper gives the relatively accurate lower bound and upper bound on it, that is, , wherec=1.22... andk>16.     

Inner Product Space and Concept Classes Induced by Bayesian Networks

Bayesian networks have become one of the major models used for statistical inference. In this paper we discuss the properties of the inner product spaces and concept class induced by some special Bayesian networks and the problem whether there exists a Bayesian network such that lower bound on dimensional inner product space just is some positive integer. We focus on two-label classification tasks over the Boolean domain. As main results we show that lower bound on the dimension of the inner product space induced by a class of Bayesian networks without v-structures is where m _i denotes the number of parents for ith variable. As the variable’s number of Bayesian network is n≤5, we also show that for each integer m∈[n+1,2 ⁿ −1] there is a Bayesian network such that VC dimension of concept class and lower bound on dimensional inner product space induced by all are m. This work was supported by National Natural Science Foundation of China (60574075).     

Chaos and asymptotical stability in discrete-time recurrent neural networks with generalized input-output function

We theoretically investigate the asymptotical stability, local bifurcations and chaos of discrete-time recurrent neural networks with the form of

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.     

On the Chebyshev Function ψ(x)

Suppose that the Riemann hypothesis is valid, and let be the Chebyshev function. In this paper, we obtain the following bound for all >1 and positive integers .     

New results for molecular formation under pairwise potential minimization

We establish new lower bounds on the distance between two points of a minimum energy configuration of N points in ℝ³ interacting according to a pairwise potential function. For the Lennard-Jones case, this bound is 0.67985 (and 0.7633 in the planar case). A similar argument yields an estimate for the minimal distance in Morse clusters, which improves previously known lower bounds. Moreover, we prove that the optimal configuration cannot be two-dimensional, and establish an upper bound for the distance to the nearest neighbour of every particle, which depends on the position of this particle. On the boundary of the optimal configuration polytope, this is unity while in the interior, this bound depends on the potential function. In the Lennard-Jones case, we get the value . Also, denoting by V _N the global minimum in an N point minimum energy configuration, we prove in Lennard-Jones clusters for all N≥2, while asymptotically holds (as opposed to in the planar case, confirming non-planarity for large N).     

Light paths with an odd number of vertices in polyhedral maps

Let P _k be a path on k vertices. In an earlier paper we have proved that each polyhedral map G on any compact 2-manifold with Euler characteristic contains a path P _k such that each vertex of this path has, in G, degree . Moreover, this bound is attained for k = 1 or k 2, k even. In this paper we prove that for each odd , this bound is the best possible on infinitely many compact 2-manifolds, but on infinitely many other compact 2-manifolds the upper bound can be lowered to .     

Strange expectations and simultaneous cores

Let \(\gcd (a,b)=1\). J. Olsson and D. Stanton proved that the maximum number of boxes in a simultaneous (a, b)-core is

$$\begin{aligned} \max _{\lambda \in {\mathrm {core}}(a,b)} (\mathsf{size}(\lambda )) = \frac{(a^2-1)(b^2-1)}{24} \end{aligned}$$

and that this maximum is achieved by a unique core. P. Johnson combined Ehrhart theory with the polynomial method to prove D. Armstrong’s conjecture that the expected number of boxes in a simultaneous (a, b)-core is

$$\begin{aligned} \mathop {\mathbb {E}}\limits _{\lambda \in {\mathrm {core}}(a,b)}\left( \mathsf{size}(\lambda )\right) = \frac{(a-1)(b-1)(a+b+1)}{24}. \end{aligned}$$

We extend Johnson’s method to compute the variance to be

$$\begin{aligned} \mathop {\mathbb {V}}\limits _{\lambda \in {\mathrm {core}}(a,b)}\left( \mathsf{size}(\lambda )\right) = \frac{ab(a-1)(b-1)(a+b)(a+b+1)}{1440}, \end{aligned}$$

and also prove polynomiality of all moments. By extending the definitions of “simultaneous cores” and “number of boxes” to affine Weyl groups, we give uniform generalizations of all three formulae above to simply laced affine types. We further explain the appearance of the number 24 using the “strange formula” of H. Freudenthal and H. de Vries.

     

Many Neighborly Polytopes and Oriented Matroids

In this paper we present a new technique to construct neighborly polytopes, and use it to prove a lower bound of ${\big (( r+d ) ^{( \frac{r}{2}+\frac{d}{2} )^{2}}\big )}\big /{\big ({r}^{{(\frac{r}{2})}^{2}} {d}^{{(\frac{d}{2})}^{2}}{\mathrm{e}^{3\frac{r}{2}\frac{d}{2}}}\big )}$ for the number of combinatorial types of vertex-labeled neighborly polytopes in even dimension d with $r+d+1$ vertices. This improves current bounds on the number of combinatorial types of polytopes. The previous best lower bounds for the number of neighborly polytopes were found by Shemer in 1982 using a technique called the Sewing Construction. We provide a new simple proof that sewing works, and generalize it to oriented matroids in two ways: to Extended Sewing and to Gale Sewing. Our lower bound is obtained by estimating the number of polytopes that can be constructed via Gale Sewing. Combining both new techniques, we are also able to construct many non-realizable neighborly oriented matroids.     

On a conjectured inequality of Gautschi and Leopardi for Jacobi polynomials

Motivated by work on positive cubature formulae over the spherical surface, Gautschi and Leopardi conjectured that the inequality holds for α,β > − 1 and n ≥ 1, θ ∈ (0, π), where are the Jacobi polynomials of degree n and parameters (α, β). We settle this conjecture in the special cases where .      

Generalization of Selberg’s $$ \frac{3}{{16}} $$ theorem and affine sieve

An analogue of the well-known \frac316 \frac{3}{{16}} lower bound for the first eigenvalue of the Laplacian for a congruence hyperbolic surface is proven for a congruence tower associated with any non-elementary subgroup L of SL(2,Z). The proof in the case that the Hausdorff of the limit set of L is bigger than \frac12 \frac{1}{2} is based on a general result which allows one to transfer such bounds from a combinatorial version to this archimedian setting. In the case that delta is less than \frac12 \frac{1}{2} we formulate and prove a somewhat weaker version of this phenomenon in terms of poles of the corresponding dynamical zeta function. These “spectral gaps” are then applied to sieving problems on orbits of such groups.     

Hybrid triple systems and cubic feedback sets

Ac-hybrid triple system of orderv is a decomposition of the completev-vertex digraph intoc cyclic tournaments of order 3 and transitive tournaments of order 3. Hybrid triple systems generalize directed triple systems (c = 0) and Mendelsohn triple systems (c = v(v – 1)/3); omitting directions yields an underlying twofold triple system. The spectrum ofv andc for which ac-hybrid triple system of orderv exists is completely determined in this paper. Using (cubic) block intersection graphs, we then show that every twofold triple system of order underlies ac-hybrid triple system with . Examples are constructed for all sufficiently largev, for which this maximum is at most . The lower bound here is proved by establishing bounds onF _i (n, r), the size of minimum cardinality vertex feedback sets inn-vertexi-connected cubic multigraphs havingr repeated edges. We establish that , 8$$ " align="middle" border="0"> . These bounds are all tight, and the latter is used to derive the lower bound in the design theoretic problem.