Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type

D. M. Barrington proved the coincidence of the class NC¹ of functions computable by the circuits of logarithmic depth with the class of functions computable by branching programs of constant width and polynomial length (BWBP). In this paper, the structure of branching programs suggested by the Barrington method is defined more exactly. Namely, it is proved that we can compute all functions from NC¹ and only them by the k-OBDDs of polynomial size and width 5. This can be reformulated as poly(n)-OBDD₅ =NC¹.     

Ore-type conditions implying 2-factors consisting of short cycles

For every graph G, let . The main result of the paper says that every n-vertex graph G with contains each spanning subgraph H all whose components are isomorphic to graphs in . This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.     

Complexity of gene circuits,Pfaffian functions and the morphogenesis problem

We consider a model of gene circuits. We show that these circuits are capable to generate any spatio–temporal patterns. We give lower bounds on the number of genes required to create a given pattern. To cite this article: S. Vakulenko, D. Grigoriev, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

The reversible context 2 in KAM theory: the first steps

The reversible context 2 in KAM theory refers to the situation where dim FixG < 1/2 codim T, here FixG is the fixed point manifold of the reversing involution G and T is the invariant torus one deals with. Up to now, this context has been entirely unexplored. We obtain a first result on the persistence of invariant tori in the reversible context 2 (for the particular case where dim Fix G = 0) using J. Moser’s modifying terms theorem of 1967.     

Collapsing monoids consisting of permutations and constants

In this paper we determine all collapsing transformation monoids that contain at least one unary constant operation and whose nonconstant operations are permutations. Furthermore, we find an infinite family of transformation monoids that consist of at least three unary constant operations and some permutations for which the corresponding monoidal intervals are 2-element chains. This research is supported by Hungarian National Foundation for Scientific Research grant nos. T 37877 and K 60148.     

DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits

The paper presents a procedure, called DB2A, for constructing a Hamiltonian circuit (HC) in a general directed graph. Application examples and a completely developed example problem are included. An appendix recalls the features of DB2, used here as a subprocedure of DB2A, and finding a Hamiltonian Cycle in undirected graphs.     

Matchings in simplicial complexes, circuits and toric varieties

Using a generalized notion of matching in a simplicial complex and circuits of vector configurations, we compute lower bounds for the minimum number of generators, the binomial arithmetical rank and the A-homogeneous arithmetical rank of a lattice ideal. Prime lattice ideals are toric ideals, i.e. the defining ideals of toric varieties.     

On the composites consisting of randomly distributed fibers

The results highlight and interpret the testing and properties of natural fibre composites including, non-destructive and high strain rate testing. The potential of this material for noise enclosures is investigated by using a coupled method cnoidal – Extended Finite Element Method (XFEM). XFEM enables the accurate approximation of solutions with jumps, discontinuities or general high gradients across interfaces. The dissipation of the sound power into a plate/cavity system shows the efficiency of this composite to achieve noise reduction better to that obtained at low and higher frequencies with traditional foams. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The deviation, density, and depth of partially ordered sets

Let P be a poset, and let γ be a linear order type with |γ| ≥ 3. The γ-deviation of P, denoted by γ-dev P, is defined inductively as follows: (1) γ-dev P=0, if P contains no chain of order type γ; (2) γ-dev P = , if γ-dev P and each chain C of type γ in P contains elements a and b such that a<b and [a, b] as an interval of P has γ-deviation <. There may be no ordinal such that γ-dev P = ; i.e., γ-dev P does not exist. A chain is γ-dense if each of its intervals contains a chain of order type γ. If P contains a γ-dense chain, then γ-dev P fails to exist. If either (1) P is linearly ordered or (2) a chain of order type γ does not contain a dense interval, then the converse holds. For an ordinal ξ, a special set S(ξ) is used to study ω_ξ-deviation. The depth of P, denoted by δ(P) is the least ordinal β that does not embed in P^*. Then the following statements are equivalent: (1) ω_ξ-dev P does not exist; (2) S(ξ) embeds in P; and (3) P has a subset Q of cardinality _ξ such that δ(Q^*) = ω_{ξ + 1}. Also ω_ξ-dev P = <ω_{ξ + 1} if and only if |δ(P^*)|_ξ; if these equivalent conditions hold, then ω^β_ξ < δ(P^*) ≤ ω ^{+ 1}_ξ for all β < . Applications are made to the study of chains of submodules of a module over an associative ring.     

Multiple zeta values of fixed weight, depth, and height

We give a generating function for the sums of multiple zeta values of fixed weight, depth and height in terms of Riemann zeta values.     

On the range of reversible random walks onZ 2 in a random environment

In this paper, a weak law of large numbers is obtained for the range of two dimensional reversible random walk in a random environment.Partly supported by NSF of China.     

Whitney smooth families of invariant tori within the reversible context 2 of KAM theory

We prove a general theorem on the persistence of Whitney C ^∞-smooth families of invariant tori in the reversible context 2 of KAM theory. This context refers to the situation where dim FixG < (codim T)/2, where FixG is the fixed point manifold of the reversing involution G and T is the invariant torus in question. Our result is obtained as a corollary of the theorem by H. W.Broer, M.-C.Ciocci, H.Hanßmann, and A.Vanderbauwhede (2009) concerning quasi-periodic stability of invariant tori with singular “normal” matrices in reversible systems.     

Depth,Stanley depth,and regularity of ideals associated to graphs

Let \({\mathbb{K}}\) be a field and \({S=\mathbb{K}[x_1,\dots,x_n]}\) be the polynomial ring in n variables over \({\mathbb{K}}\). Let G be a graph with n vertices. Assume that \({I=I(G)}\) is the edge ideal of G and \({J=J(G)}\) is its cover ideal. We prove that \({{\rm sdepth}(J)\geq n-\nu_{o}(G)}\) and \({{\rm sdepth}(S/J)\geq n-\nu_{o}(G)-1}\), where \({\nu_{o}(G)}\) is the ordered matching number of G. We also prove the inequalities \({{\rmsdepth}(J^k)\geq {\rm depth}(J^k)}\) and \({{\rm sdepth}(S/J^k)\geq {\rmdepth}(S/J^k)}\), for every integer \({k\gg 0}\), when G is a bipartite graph. Moreover, we provide an elementary proof for the known inequality reg\({(S/I)\leq \nu_{o}(G)}\).     

Remark on minimization of depth of Boolean circuits

It is shown that Lozhkin’s method (1981) for minimization of the depth of formulas with a bounded number of changing types of elements in paths from input to output and Hoover-Klawe-Pippenger’s method (technical report in 1981, journal publication in 1984) for minimization of the depth of circuits with unbounded branching by insertion of trees from buffers with bounded branching of outputs for each buffer are dual to each other and can be proved by one and the same method.     

Delay optimization of linear depth boolean circuits with prescribed input arrival times

We consider boolean circuits C over the basis Ω={,} with inputs x₁, x₂,…,x_n for which arrival times are given. For 1in we define the delay of x_i in C as the sum of t_i and the number of gates on a longest directed path in C starting at x_i. The delay of C is defined as the maximum delay of an input.Given a function of the form

f(x₁,x₂,…,x_n)=g_n−1(g_n−2(…g₃(g₂(g₁(x₁,x₂),x₃),x₄)…,x_n−1),x_n)