Search

We note a simple algebraic proof of Frolkina’s result that [Formula: see text] does not contain uncountably many pairwise disjoint copies of the Möbius band, and of a similar result in higher dimensions.

The inequality between rank and crank moments was conjectured and later proved by Garvan himself in 2011. Recently, Dixit and the authors introduced finite analogues of rank and crank moments for vector partitions while deriving a finite analogue of Andrews’ famous identity for smallest parts function. In the same paper, they also conjectured an inequality between finite analogues of rank and crank moments, analogous to Garvan’s conjecture. In this paper, we give a proof of this conjecture.

Let [Formula: see text] denote the probability space of random 2-dimensional simplicial complexes in the Linial–Meshulam model, and let [Formula: see text] denote a random complex chosen according to this distribution. In a paper of Cohen, Costa, Farber and Kappeler, it is shown that for [Formula: see text] with high probability [Formula: see text] is free. Following that, a paper of Costa and Farber shows that for values of [Formula: see text] which satisfy [Formula: see text] with high probability, [Formula: see text] is not free. Here, we improve on both these results to show that there are explicit constants [Formula: see text], so that for [Formula: see text] with high probability [Formula: see text] has free fundamental group and that for [Formula: see text] with high probability [Formula: see text] has fundamental group which either is not free or is trivial.

The consecutive linear [Formula: see text]-out-of-[Formula: see text]-from-[Formula: see text]:F system consists of [Formula: see text] linear ordered components and the consecutive circular [Formula: see text]-out-of-[Formula: see text]-from-[Formula: see text]:F system consists of [Formula: see text] circular ordered components. In this paper, we suggest, for the first time, modeling and exact reliability for these models. The linear system fails if and only if there exists a [Formula: see text]-order statistic of [Formula: see text]-consecutive [Formula: see text] [Formula: see text] of components in the failed state, [Formula: see text], [Formula: see text]; and the circular system fails if and only if there exists a [Formula: see text]-order statistic of [Formula: see text]-consecutive [Formula: see text] [Formula: see text] of components in the failed state, [Formula: see text], [Formula: see text]. In this paper, we designed an innovative algorithm to obtain the exact reliability for an extensive class of consecutive linear and circular systems. In continuation, there are the MATLAB Programs of exact reliability for consecutive linear and circular systems. In the following, we applied comparative and numerical results and calculated the exact reliability of this strategic systems. Finally, we calculated the exact reliability for two real-world practical examples.

Let $b,n\in \mathbb{Z}$, $n\geq 1$, and ${\cal D}_1, \ldots, {\cal D}_{\tau(n)}$ be all positive divisors of $n$. For $1\leq l \leq \tau(n)$, define ${\cal C}_l:=\lbrace 1 \leqslant x\leqslant n \; : \; (x,n)={\cal D}_l\rbrace$. In this paper, by combining ideas from the finite Fourier transform of arithmetic functions and Ramanujan sums, we give a short proof for the following result: the number of solutions of the linear congruence $x_1+\cdots +x_k\equiv b \pmod{n}$, with $\kappa_{l}=|\lbrace x_1, \ldots, x_k \rbrace \cap {\cal C}_l|$, $1\leq l \leq \tau(n)$, is \begin{align*} \frac{1}{n}\mathlarger{\sum}_{d\, \mid \, n}c_{d}(b)\mathlarger{\prod}_{l=1}^{\tau(n)}\left(c_{\frac{n}{{\cal D}_l}}(d)\right)^{\kappa_{l}}, \end{align*} where $c_{d}(b)$ is a Ramanujan sum. Some special cases and other forms of this problem have been already studied by several authors. The problem has recently found very interesting applications in number theory, combinatorics, computer science, and cryptography. The above explicit formula generalizes the main results of several papers, for example, the main result of the paper by Sander and Sander [J. Number Theory {\bf 133} (2013), 705--718], one of the main results of the paper by Sander [J. Number Theory {\bf 129} (2009), 2260--2266], and also gives an equivalent formula for the main result of the paper by Sun and Yang [Int. J. Number Theory {\bf 10} (2014), 1355--1363].

By proving precisely which singularity index lists arise from the pair of invariant foliations for a pseudo-Anosov surface homeomorphism, Masur and Smillie [24] determined a Teichmüller flow invariant stratification of the space of quadratic differentials. In this final paper of a three-paper series, we give a first step to an [Formula: see text] analog of the Masur–Smillie theorem. Since the ideal Whitehead graphs defined by Handel and Mosher [16] give a strictly finer invariant in the analogous [Formula: see text] setting, we determine which of the 21 connected, simplicial, five-vertex graphs are ideal Whitehead graphs of fully irreducible outer automorphisms in [Formula: see text]. The rank 2 case is actually a direct consequence of the work of Masur and Smillie, as all elements of [Formula: see text] are induced by surface homeomorphisms and the index list and ideal Whitehead graph for a surface homeomorphism give precisely the same data.

In this paper, we obtain the crosscap number of any alternating knots by using our recently-introduced diagrammatic knot invariant (Theorem 1). The proof is given by properties of chord diagrams (Kindred proved Theorem 1 independently via other techniques). For non-alternating knots, we give Theorem 2 that generalizes Theorem 1. We also improve known formulas to obtain upper bounds of the crosscap number of knots (alternating or non-alternating) (Theorem 3). As a corollary, this paper connects crosscap numbers and our invariant with other knot invariants such as the Jones polynomial, twist number, crossing number, and hyperbolic volume (Corollaries 1–7). In Appendix A, using Theorem 1, we complete giving the crosscap numbers of the alternating knots with up to 11 crossings including those of the previously unknown values for [Formula: see text] knots (Tables A.1).

In this paper, we introduce a new operator in order to derive some new symmetric properties of [Formula: see text]-Fibonacci and [Formula: see text]-Lucas numbers and Fibonacci polynomials. By making use of the new operator defined in this paper, we give some new generating functions for [Formula: see text]-Fibonacci and Pell numbers and Fibonacci polynomials.

We first prove the following: Let [Formula: see text] and [Formula: see text]. Let [Formula: see text] and [Formula: see text] be closed, oriented, [Formula: see text]-dimensional [Formula: see text]-connected, simple submanifolds of [Formula: see text]. Then [Formula: see text] and [Formula: see text] are isotopic if and only if a Seifert matrix associated with a simple Seifert hypersurface for [Formula: see text] is [Formula: see text]-[Formula: see text]-equivalent to that for [Formula: see text]. We also discuss the [Formula: see text] case. This result implies one of our main results: Let [Formula: see text]. A 1-link [Formula: see text] is pass-equivalent to a 1-link [Formula: see text] if and only if [Formula: see text] is [Formula: see text]-pass-equivalent to [Formula: see text]. Here, [Formula: see text] means the knot product of [Formula: see text] and [Formula: see text], and [Formula: see text] means [Formula: see text]. See the body of the paper for the definition of knot products. It also implies the other main results: We strengthen the authors’ old result that two-fold cyclic suspension commutes with the performance of the twist move for spherical [Formula: see text]-knots. See the body for the precise statement. Furthermore, it implies the following: Let [Formula: see text] and [Formula: see text]. Let [Formula: see text] be a closed oriented [Formula: see text]-submanifold of [Formula: see text]. Then [Formula: see text] is a Brieskorn submanifold if and only if [Formula: see text] is [Formula: see text]-connected, simple and has a [Formula: see text]-Seifert matrix associated with a simple Seifert hypersurface that is [Formula: see text]-[Formula: see text]-equivalent to a [Formula: see text]-type (see the body of the paper for a definition). We also discuss the [Formula: see text] case.

In a recent paper, we studied the interaction between the automorphism group of a graph and its Tutte polynomial. More precisely, we proved that certain symmetries of graphs are clearly reflected by their Tutte polynomials. The purpose of this paper is to extend this study to other graph polynomials. In particular, we prove that if a graph [Formula: see text] has a symmetry of prime order [Formula: see text], then its characteristic polynomial, with coefficients in the finite field [Formula: see text], is determined by the characteristic polynomial of its quotient graph [Formula: see text]. Similar results are also proved for some generalization of the Tutte polynomial.

In a network environment supporting mobile entities (called robots or agents), a black hole is a harmful site that destroys any incoming entity without leaving any visible trace. The black-hole search problit is the task of a team of k > 1 mobile entities, starting from the same safe location and executing the same algorithm, to determine within finite time the location of the black hole. In this paper, we consider the black hole search problit in asynchronous ring networks of n nodes, and focus on time complexity. It is known that any algorithm for black-hole search in a ring requires at least 2(n - 2) time in the worst case. The best known algorithm achieves this bound with a team of n - 1 agents with an average time cost of 2(n - 2), equal to the worst case. In this paper, we first show how the same number of agents using 2 extra time units in the worst case, can solve the problit in only [Formula: see text] time on the average. We then prove that the optimal average case complexity of [Formula: see text] can be achieved without increasing the worst case using 2(n - 1) agents. Finally, we design an algorithm that achieves asymptotically optimal both worst and average case time complexities itploying an optimal team of k = 2 agents, thus improving on the earlier results that required O(n) agents.

In the paper [13], for an arbitrary virtual link [Formula: see text], three groups [Formula: see text], [Formula: see text], [Formula: see text] and [Formula: see text] were defined. In the present paper, these groups for the virtual trefoil are investigated. The structure of these groups are found out and the fact that some of them are not isomorphic to each other is proved. Also, we prove that [Formula: see text] distinguishes the Kishino knot from the trivial knot. The fact that these groups have the lower central series which does not stabilize on the second term is noted. Hence, we have a possibility to study these groups using quotients by terms of the lower central series and to construct representations of these groups in rings of formal power series. It allows to construct an invariants for virtual knots.

Let $a,b,c $ be any positive integers such that $c\mid ab$ and $d_i^\pm$ is a square free positive integer of the form $d_i^\pm=a^{2k} b^{2l}\pm i c^m$ where $k,l \geq m$ and $i=1,2.$ The main focus of this paper to find the fundamental solution of the equation $ x^2-d_i^\pm y^2=1$ with the help of the continued fraction of $\sqrt{d_i^\pm}.$ We also obtain all the positive solutions of the equations $ x^2-d_i^\pm y^2=\pm 1$ and $ x^2-d_i^\pm y^2=\pm 4$ by means of the Fibonacci and Lucas sequences. Furthermore, in this work, we derive some algebraic relations on the Pell form $ F_{d_i^\pm}(x, y) = x^2-d_i^\pm y^2 $ including cycle, proper cycle, reduction and proper automorphism of it. We also determine the integer solutions of the Pell equation $ F_{\Delta_{d_i^\pm}} (x, y) = 1 $ in terms of $d_i^\pm. We generalized all the results of the papers [2], [9], [26], and [37]., Comment: 16 pages

The n-dimensional hypercube Qn is bipancyclic and contains a 3-regular, 3-connected subgraph on l vertices for every even l from 8 to 2n except 10. In this paper, we strengthen the previous works to Cartesian product of paths. The bipancyclicity and the existence of 3-regular subgraphs of Cartesian product of paths are studied in this paper.

In this paper, we investigate twist sequences for Kauffman finite-type invariants and Goussarov–Polyak–Viro finite-type invariants. It is shown that one obtains a Kauffman or GPV type of degree ≤ n if and only if an invariant is a polynomial of degree ≤ n on every twist lattice of the right form. The main result of this paper is an application of this technique to the coefficients of the Jones–Kauffman polynomial. It is shown that the Kauffman finite-type invariants obtained from these coefficients are not GPV finite-type invariants of any degree by explicitly showing they can never be polynomials. This generalizes a result of Kauffman [8], where it is known for degree k = 2.

We proved by computer enumeration that the Jones polynomial distinguishes the unknot for knots up to 22 crossings. Following an approach of Yamada, we generated knot diagrams by inserting algebraic tangles into Conway polyhedra, computed their Jones polynomials by a divide-and-conquer method, and tested those with trivial Jones polynomials for unknottedness with the computer program SnapPy. We employed numerous novel strategies for reducing the computation time per knot diagram and the number of knot diagrams to be considered. That made computations up to 21 crossings possible on a single processor desktop computer. We explain these strategies in this paper. We also provide total numbers of algebraic tangles up to 18 crossings and of Conway polyhedra up to 22 vertices. We encountered new unknot diagrams with no crossing-reducing pass moves in our search. We report one such diagram in this paper., 19 pages, Journal of Knot Theory and Its Ramifications, (2018) 27, 1840009

The purpose of this paper is to give the homotopy classification of nanophrases of length 2 with 4 letters. To do it we construct some new invariants of nanophrases γ and T. The invariant γ defined in this paper is an extension of the invariant γ for nanowords introduced by Turaev. The invariant T is a new invariant of nanophrases. As a corollary of these results, we give the classification of two-component pointed, ordered, oriented curves on surfaces with minimum crossing number less than or equal to 2.

This paper deals with dynamic systems described by sets of ordinary differential equations. As described in a previous paper [Thomas & Kaufman, 2005], phase space can be partitioned according to the signs of the eigenvalues of the Jacobian matrix and the slopes of its eigenvectors, using "frontiers" described by simple analytic expressions. In the present paper, we develop this approach with special emphasis on: — a preliminary, qualitative, yet quite efficient, description based simply on the sign patterns of elements of the Jacobian matrix — the identification and characterization of two additional frontiers based on the relative slopes of the eigenvectors (in two dimensions only) — the applicability to systems of higher dimensionalities — programs (in Mathematica) that provide immediately the phase space frontier diagrams from the ODE's for two- (Appendix 2) and n-dimensional systems (Appendix 3) For systems of sufficiently low dimensionality, the resulting diagrams give a global view of the structure of phase space, partitioned into domains each consistent as regards to the nature of any steady state that might be present in that domain. Fortunately, the dimensionality of phase space frontier diagrams depends not on the overall dimensionality of the system but on the number of variables that carry nonlinearity; an n-variable system in which only two variables carry nonlinearity can be described by a two-dimensional diagram.

This paper continues our quest to develop a rigorous analytical theory of 1-D cellular automata via a nonlinear dynamics perspective. The 18 yet uncharacterized local rules are henceforth partitioned into ten complex Bernoulliστ-shift rules and eight hyper Bernoulliστ-shift rules, the latter including such famous rules [Formula: see text] and [Formula: see text]. All exhibit a bizarre composite wave dynamics with arbitrarily large Bernoulli velocity σ and Bernoulli return time τ as the length L → ∞. Basin tree diagrams of all ten complex Bernoulli στ-shift rules are exhibited for lengths L = 3, 4, …, 8. Superficial as it may seem, these basin tree diagrams suggest general qualitative properties which have since been proved to be true in general. Two such properties form the main results of this paper; namely, [Formula: see text] Explicit global state transition formulas are given for local rules [Formula: see text], [Formula: see text] and [Formula: see text]. Such formulas led to the rigorous proof of several surprising periodicity constraints for rule [Formula: see text], and to the discovery of a new global, quasi-equivalence class, defined via an alternating transformation. In particular, local rules [Formula: see text] and [Formula: see text]are globally quasi-equivalent where corresponding space-time patterns can be derived from each other by simply complementing every other row. Another important result of this paper is the discovery of a scale-free phenomenon exhibited by the local rules [Formula: see text], [Formula: see text] and [Formula: see text]. In particular, the period "T" of all attractors of rules [Formula: see text], [Formula: see text] and [Formula: see text], as well as of all isles of Eden of rules [Formula: see text] and [Formula: see text], increases linearly with unit slope, in logarithmic scale, with the length L.

This paper deals with a special kind of complex systems which depend on an arbitrary (and usually large) number n of random Boolean variables. The so-called complex stochastic Boolean systems often appear in many different scientific, technical or social areas. Clearly, there are 2n binary states associated to such a complex system. Each one of them is given by a binary string u = (u1,…,un) ∈ {0, 1}n of n bits, which has a certain occurrence probability Pr {u}. The behavior of a complex stochastic Boolean system is determined by the current values of its 2n binary n-tuple probabilities Pr {u} and by the ordering between pairs of them. Hence, the intrinsic order graph provides a useful representation of these systems by displaying (scaling) the 2n binary n-tuples which are ordered in decreasing probability of occurrence. The intrinsic order reduces the complexity of the problem from exponential (2n binary n-tuples) to linear (n Boolean variables). For any fixed binary n-tuple u, this paper presents a new, simple algorithm enabling rapid, elegant determination of all the binary n-tuples v with occurrence probabilities less than or equal to (greater than or equal to) Pr {u}. This algorithm is closely related to the lexicographic (truth-table) order in {0, 1}n, and this is illustrated through the connections (paths) in the intrinsic order graph.

A Chaitin Omega number is the halting probability of a universal prefix-free Turing machine. Every Omega number is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable. The value of an Omega number is highly machine-dependent. In general, no more than finitely many scattered bits of the binary expansion of an Omega number can be exactly computed; but, in some cases, it is possible to prove that no bit can be computed. In this paper, we will simplify and improve both the method and correctness of the proof proposed in an earlier paper, and we will compute the exact approximations of two Omega numbers of the same prefix-free Turing machine, which is universal when used with data in base 16 or base 2: we compute 43 exact bits for the base 16 machine and 40 exact bits for the base 2 machine.

In this paper, we study the dynamical behavior of nonautonomous, almost-periodic discrete FitzHugh–Nagumo system defined on infinite lattices. We prove that the nonautonomous infinite-dimensional system has a uniform attractor which attracts all solutions uniformly with respect to the translations of external terms. We also establish the upper semicontinuity of uniform attractors when the infinite-dimensional system is approached by a family of finite-dimensional systems. This paper is based on a uniform tail method, which shows that, for large time, the tails of solutions are uniformly small with respect to bounded initial data as well as the translations of external terms. The uniform tail estimates play a crucial role for proving the uniform asymptotic compactness of the system and the upper semicontinuity of attractors.

Chua Oscillator and its generalizations display a variety of chaotic behaviors, whose most startling manifestation is the presence of strange attractors. These come in many different shapes and sizes yet share a special kind of beauty. In the work reported in this paper, we explored the universe of these attractors — much of which is still virgin territory. We then recorded the most interesting and significant in a "Gallery of Chua attractors". In papers, published in previous issues of this journal, we showed how different versions of the Oscillator follow different "routes to chaos". Parts II–IV of the Gallery describe the attractors generated by the dimensional and dimensionless forms of the Oscillator as well as attractors generated by circuits with a cubic equation for the characteristic function of the Chua diode. Here, we provide a detailed discussion of single scroll Chua systems and present 248 attractors generated by such systems. For each attractor, we provide a three-dimensional image, time series and FFTs. We go on to describe the techniques used to create the Gallery and the main characteristics of the attractors it includes. We use techniques such as PCA to represent the gallery in parameter space. The same techniques allow us to manipulate the shape of the attractors by enlarging them along their main axes of development. We use Hausdorff distances to compare shapes, and exploit the results to create landscapes in parameter space. Finally, we present experimental data from a single scroll attractor, using inertial ellipsoids and Hausdorff distances to show how the shape of the attractor evolves.

In a previous paper we showed that, for any $n \ge m+2$, most sets of $n$ points in $\RR^m$ are determined (up to rotations, reflections, translations and relabeling of the points) by the distribution of their pairwise distances. But there are some exceptional point configurations which are not reconstructible from the distribution of distances in the above sense. In this paper, we present a reconstructibility test with running time $O(n^{11})$. The cases of orientation preserving rigid motions (rotations and translations) and scalings are also discussed., 10 pages

In this paper we prove a Markov Theorem for virtual braids and for some analogs of this structure. The virtual braid group is the natural companion in the category of virtual knots, just as the Artin braid group is the natural companion to classical knots and links. In this paper we follow the L--move methods to prove the Virtual Markov Theorem. One benefit of this approach is a fully local algebraic formulation of the Theorem., Comment: 42 pages, 42 figures, LaTeX document

In a preceding paper, Bruyère and Carton introduced automata, as well as rational expressions, which allow to deal with words indexed by linear orderings. A Kleene-like theorem was proved for words indexed by countable scattered linear orderings. In this paper we extend this result to languages of words indexed by all linear orderings.

The subject of this paper is a generalized approach to relative scalar cardinalities of fuzzy sets. In the main part of the paper, we discuss basic properties of triangular norm-based relative cardinality such as valuation property, the cartesian product rule and complementary rule. Examples of cardinalities satisfying those properties are also given.

The main result of this paper states that, if every cyclic modification of a d-regular digraph has super line-connectivity d, then the line digraph also has super line-connectivity d. Since many well-known interconnection network topologies, such as the Kautz digraphs, the de Bruijn digraphs, etc., can be constructed by iterating the line digraph construction, our result leads to several known and new connectivity results for these topologies, as shown later in the paper.

In this paper we study phase space relations in a certain class of discrete dynamical systems over graphs. The systems we investigate are called Sequential Dynamical Systems (SDSs), which are a class of dynamical systems that provide a framework for analyzing computer simulations. Specifically, an SDS consists of (i) a finite undirected graph Y with vertex set {1,2,…,n} where each vertex has associated a binary state, (ii) a collection of Y-local functions (Fi,Y)i∈ v [Y] with [Formula: see text] and (iii) a permutation π of the vertices of Y. The SDS induced by (i)–(iii) is the map [Formula: see text] The paper is motivated by a general reduction theorem for SDSs which guarantees the existence of a phase space embedding induced by a covering map between the base graphs of two SDSs. We use this theorem to obtain information about phase spaces of certain SDSs over binary hypercubes from the dynamics of SDSs over complete graphs. We also investigate covering maps over binary hypercubes, [Formula: see text], and circular graphs, Circ n. In particular we show that there exists a covering map [Formula: see text] if and only if 2n≡0 mod n+1. Furthermore, we provide an interpretation of a class of invertible SDSs over circle graphs as right-shifts of length n-2 over {0,1}2n-2. The paper concludes with a brief discussion of how we can extend a given covering map to a covering map over certain extended graphs.

This paper studies certain relations among vertex algebras, vertex Lie algebras and vertex Poisson algebras. In this paper, the notions of vertex Lie algebra (conformal algebra) and vertex Poisson algebra are revisited and certain general construction theorems of vertex Poisson algebras are given. A notion of filtered vertex algebra is formulated in terms of a notion of good filtration and it is proved that the associated graded vector space of a filtered vertex algebra is naturally a vertex Poisson algebra. For any vertex algebra V, a general construction and a classification of good filtrations are given. To each ℕ-graded vertex algebra V=∐n∈ℕV(n) with [Formula: see text], a canonical (good) filtration is associated and certain results about generating subspaces of certain types of V are also obtained. Furthermore, a notion of formal deformation of a vertex (Poisson) algebra is formulated and a formal deformation of vertex Poisson algebras associated with vertex Lie algebras is constructed.

The graph C*-algebra of a directed graph E is the universal C*-algebra generated by a family of partial isometries satisfying relations which reflect the path structure of E. In the first part of this paper we consider coverings of directed graphs: morphisms p:F->E which are local isomorphisms. We show that the graph algebra C*(F) can be recovered from C*(E) as a crossed product by a coaction of a homogeneous space associated to the fundamental group ��_1 (E). These crossed products provide a good model for a general theory of crossed products by homogeneous spaces. The second part of the paper is devoted to building a framework for studying crossed products by homogeneous spaces using Rieffel's theory of proper actions., 15 pages with no figures

Let μ := (μt)t > 0 be a convolution semigroup on ℝd endowed with its Lebesgue measure λ. Let ℳ(μ) be the set of all positive Borel measures ω on ℝd for which μt * ω ≪ λ, for each t > 0. Let EX(μ) be the set of all exit laws of μ, i.e.the set of Borel functions φ :]0, ∞[× ℝd ↦ [0, ∞] which verifies the functional equation (by putting φt := φ(t, .)) [Formula: see text] Under some λ-regularity assumptions, it is proved in this paper that EX(μ) can be identified with ℳ(μ). Moreover, let μβ be the convolution semigroup obtained by subordination of μ by a subordinator β (i.e. [Formula: see text] where β is a convolution semigroup on [0,∞[). It is also proved in this paper that, an exit law ψ of μβ is subordinated to some exit law of μ, if and only if ω belongs to ℳ(μ) where ω ∈ ℳ(μβ) is the associated measure to ψ by the preceding identification.

The concept of entropy is an important part of the theory of additive measures. In this paper, a definition of entropy is introduced for general (not necessarily additive) measures as the infinum of the Shannon entropies of "subordinate" additive measures. Several properties of the general entropy are discussed and proved. Some of the properties require that the measure belongs to the class of so-called "equientropic" general measures introduced and studied in this paper. The definition of general entropy is extended to the countable case for which a sufficient condition of convergence is proved. We introduce a method of "conditional combination" of general measures and prove that in that case the general entropy possesses the "subset independence" property.

International audience; The notion of independence is central in many information processing areas, such as multiple criteria decision making, databases, or uncertain reasoning. This is especially true in the later case, where the success of Bayesian networks is basically due to the graphical representation of independence they provide. This paper first studies qualitative independence relations when uncertainty is encoded by a complete pre-order between states of the world. While a lot of work has focused on the formulation of suitable definitions of independence in uncertainty theories our interest in this paper is rather to formulate a general definition of independence based on purely ordinal considerations, and that applies to all weakly ordered settings. The second part of the paper investigates the impact of the embedding of qualitative independence relations into the scale-based possibility theory. The absolute scale used in this setting enforces the commensurateness between local pre-orders (since they share the same scale). This leads to an easy decomposability property of the joint distributions into more elementary relations on the basis of the independence relations. Lastly we provide a comparative study between already known definition of possibilistic independence and the ones proposed here. Keywords: Knowledge representation; possibilistic independence; weakly ordered setting.

Suppose [Formula: see text] is a finite field extension of [Formula: see text] containing a primitive [Formula: see text]th root of unity. Let [Formula: see text] be a maximal [Formula: see text]-extension of [Formula: see text] with the Galois group of period [Formula: see text] and nilpotent class [Formula: see text]. In this paper, we develop formalism which allows us to study the structure of [Formula: see text] via methods of Lie theory. In particular, we introduce an explicit construction of a Lie [Formula: see text]-algebra [Formula: see text] and an identification [Formula: see text], where [Formula: see text] is a [Formula: see text]-group obtained from the elements of [Formula: see text] via the Campbell–Hausdorff composition law. In the next paper, we apply this formalism to describe the ramification filtration [Formula: see text] and an explicit form of the Demushkin relation for [Formula: see text].

A persistent lamination for a knot K is an essential lamination in the complement of K, which remains essential after every non-trivial Dehn surgery along K. Having a persistent lamination implies, for example, that every manifold obtained by non-trivial Dehn surgery along K has universal cover R^3. In this paper we present a method for building persistent laminations for knots from an incompressible Seifert surface for some `parent' knot. Using this construction, we can, for example, currently build persistent laminations for approximately 45 percent of the knots in the standard knot tables; see page 12 of the paper, or http://www.math.unt.edu/~britten/ldt/knots/knotlst1.html, for the exact list., 14 pages, with 15 figures

This paper introduces a three-way two-dimensional probabilistic Turing machine (tr2-ptm), and investigates several properties of the machine. The tr2-ptm is a two-dimensional probabilistic Turing machine (2-ptm) whose input head can only move left, right, or down, but not up. Let 2-ptms (resp. tr2-ptms) denote a 2-ptm (resp. tr2-ptm) whose input tape is restricted to square ones, and let 2-PTMs(S(n)) (resp. TR2-PTMs(S(n))) denote the class of sets recognized by S(n) space-bounded 2-ptms's (resp. tr2-ptms's) with error probability less than ½, where S(n): N→N is a function of one variable n (= the side-length of input tapes). Let TR2-PTM(L(m,n)) denote the class of sets recognized by L(m,n) space-bounded tr2-ptm's with error probability less than ½, where L(m,n): N2→N is a function of two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes). The main results of this paper are: (1) 2-NFAs - TR2-PTMs(S(n))≠ϕ for any S(n)=o(log n), where 2-NFAs denotes the class of sets of square tapes accepted by two-dimensional nondeterministic finite automata, (2) TR2-PTMsS(n)[Formula: see text]2-PTMs(S(n)) for any S(n)=o(log n), and (3) for any function g(n)=o(log n) (resp. g(n)=o(log n/log log n)) and any monotonic nondecreasing function f(m) which can be constructed by some one-dimensional deterministic Turing machine, TR2-PTM(f(m)+g(n)) (resp. TR2-PTM(f(m)×g(n))) is not closed under column catenation, column closure, and projection. Additionally, we show that two-dimensional nondeterministic finite automata are equivalent to two-dimensional probabilistic finite automata with one-sided error in accepting power.

Let $\ell, n$ be positive integers such that $\ell\geq n$. Let $\mathbb{G}_{n,\ell}$ be the Grassmannian which consists of the set of $n$-dimensional subspaces of $\mathbb{C}^{\ell}$. There is a $\mathbb{Z}$-graded algebra isomorphism between the cohomology $H^*(\mathbb{G}_{n,\ell},\mathbb{Z})$ of $\mathbb{G}_{n,\ell}$ and a natural $\mathbb{Z}$-form $B$ of the $\mathbb{Z}$-graded basic algebra of the type $A$ cyclotomic nilHecke algebra $H_{\ell,n}^{(0)}=\langle\psi_1,\cdots,\psi_{n-1},y_1,\cdots,y_n\rangle$. In this paper, we show that the isomorphism can be chosen such that the image of each (geometrically defined) Schubert class $(a_1,\cdots,a_{n})$ coincides with the basis element $b_{\mathbf{\lambda}}$ constructed by Jun Hu and Xinfeng Liang by purely algebraic method, where $0\leq a_1\leq a_2\leq\cdots\leq a_{n}\leq \ell-n$ with $a_i\in\mathbb{Z}$ for each $i$, $\mathbf{\lambda}$ is the $\ell$-multipartition of $n$ associated to $(\ell+1-(a_{n}+n), \ell+1-(a_{n-1}+n-1),\cdots,\ell+1-(a_1+1))$. A similar correspondence between the Schubert class basis of the cohomology of the Grassmannian $\mathbb{G}_{\ell-n,\ell}$ and the $b_{\lambda}$'s basis of the natural $\mathbb{Z}$-form $B$ of the $\mathbb{Z}$-graded basic algebra of $H_{\ell,n}^{(0)}$ is also obtained. As an application, we obtain a second version of Giambelli formula for Schubert classes., Comment: corrected a number of typos and added one corollary in the last section

Denote by $G$ a finite group and by $\psi(G)$ the sum of element orders in $G$. If $t$ is a positive integer, denote by $C_t$ the cyclic group of order $t$ and write $\psi(t)=\psi(C_t)$. In this paper we proved the following Theorem A: Let $G$ be a non-cyclic group of odd order $n=qm$, where $q$ is the smallest prime divisor of $n$ and $(m,q)=1$. Then the following statements hold. (1) If $q=3$, then $\frac {\psi(G)}{\psi(|G|)}\leq \frac {85}{301}$, and equality holds if and only if $n=3\cdot 7\cdot m_1$ with $(m_1,42)=1$ and $G=(C_7\rtimes C_3)\times C_{m_1}$, with $C_7\rtimes C_3$ non-abelian. (2) If $q>3$, then $\frac {\psi(G)}{\psi(|G|)}\leq \frac {p^4+p^3-p^2+1}{p^5+1}$, where $p$ is the smallest prime bigger than $q$ and equality holds if and only if $n=qp^2m_1$ with $(m_1,p!)=1$ and $G=C_q\times C_p\times C_p \times C_{m_1}$.

An (m, n)-simple 1 in a binary image I has the property that its deletion “preserves topology” when m-adjacency is used on the 1’s and n-adjacency on the 0’s of I. This paper presents new, easily visualized, necessary and sufficient conditions for a 1 in I to be (m, n)-simple, for (m, n)=(26, 6), (18, 6), (6, 26) or (6, 18) when I is a 3-d image and (m, n)=(8, 4) or (4, 8) when I is a 2-d image. Systematic and fairly general methods of verifying that a given parallel thinning algorithm always preserves topology are described, for the cases where 8-/26-adjacency is used on the 1’s and 4-/6-adjacency on the 0’s, or vice versa. The verification methods for 2-d algorithms are mainly due to Ronse and Hall; the methods for 3-d algorithms were found by Ma and Kong. New proofs are given of the correctness of these verification methods, using the characterizations of simple 1’s presented in this paper.

A linear k-forest is a forest whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted bylak(G), is the least number of linear k-forests needed to decompose G. Recently, Zuo, He, and Xue studied the exact values of the linear(n−1)-arboricity of Cartesian products of various combinations of complete graphs, cycles, complete multipartite graphs. In this paper, for general k we show thatmax{lak(G),lal(H)}≤lamax{k,l}(G□H)≤lak(G)+lal(H)for any two graphs G and H. Denote byG∘H, G×HandG⊠Hthe lexicographic product, direct product and strong product of two graphs G and H, respectively. For any two graphs G and H, we also derive upper and lower bounds oflak(G∘H),lak(G×H)andlak(G⊠H)in this paper. The linear k-arboricity of a 2-dimensional grid graph, a r-dimensional mesh, a r-dimensional torus, a r-dimensional generalized hypercube and a hyper Petersen network are also studied.

The ground state energies of the [Formula: see text] coset theories, perturbed by the [Formula: see text] operator, and those of the sine-Gordon theory, for special values of the coupling constant in the attracting regime, are the same. In the first part of this paper we extend these results to the [Formula: see text] cases. In the second part, we analyze the algebraic Bethe ansatz procedure for special points in the repulsive region. We find a one-to-one “duality” correspondence between these theories and those studied in the first part of the paper. We use the gluing procedure at the massive node proposed by Fendley and Intriligator in order to obtain the TBA systems for the generalized parafermionic supersymmetric sine-Gordon model. In the third part we propose the TBA equations for the whole class of perturbed coset models [Formula: see text] with the operator [Formula: see text] and G a nonsimplylaced group generated by one of the [Formula: see text], ℱ4, ℬn, [Formula: see text] algebras.

A new class of interconnection networks based on a family of graphs, called cubic graphs are introduced. These latter graphs arise as Cayley graphs of certain subgroups of the symmetric group. It turns out that these Cayley graphs are a hybrid between the binary hypercube and the star graph, and hence are called cubic star graphs, and are denoted by CS(m, n), m≥1 and n≥1. CS(m, n) inherits several of the properties of the hypercube and the star graph. In this paper, we present an analysis of the symmetric and topological properties. In particular, it is shown that CS(m, n) is edge transitive and hence maximally fault tolerant. We give an algorithm for finding the shortest path and provide an enumeration of the node disjoint paths. Optimal algorithms for single source and all-source broadcasting (also called gossiping) are derived. It is shown that CS(m, n) is Hamiltonian and interesting embeddings of several cycles, grids, and binary trees are derived. The paper concludes with a comparison of CS(m, n) with the binary hypercube and the star graph.

By the density of a finite graph we mean its average vertex degree. For an [Formula: see text]-generated group, the density of its Cayley graph in a given set of generators, is the supremum of densities taken over all its finite subgraphs. It is known that a group with [Formula: see text] generators is amenable if and only if the density of the corresponding Cayley graph equals [Formula: see text]. A famous problem on the amenability of R. Thompson’s group [Formula: see text] is still open. Due to the result of Belk and Brown, it is known that the density of its Cayley graph in the standard set of group generators [Formula: see text], is at least [Formula: see text]. This estimate has not been exceeded so far. For the set of symmetric generators [Formula: see text], where [Formula: see text], the same example only gave an estimate of [Formula: see text]. There was a conjecture that for this generating set equality holds. If so, [Formula: see text] would be non-amenable, and the symmetric generating set would have the doubling property. This would mean that for any finite set [Formula: see text], the inequality [Formula: see text] holds. In this paper, we disprove this conjecture showing that the density of the Cayley graph of [Formula: see text] in symmetric generators [Formula: see text] strictly exceeds [Formula: see text]. Moreover, we show that even larger generating set [Formula: see text] does not have doubling property.

Recently, Hirschhorn and the first author considered the parity of the function $a(n)$ which counts the number of integer partitions of $n$ wherein each part appears with odd multiplicity. They derived an effective characterization of the parity of $a(2m)$ based solely on properties of $m.$ In this note, we quickly reprove their result, and then extend it to an explicit characterization of the parity of $a(n)$ for all $n\not\equiv 7 \pmod{8}.$ We also exhibit some infinite families of congruences modulo 2 which follow from these characterizations. We conclude by discussing the case $n\equiv 7 \pmod{8}$, where, interestingly, the behavior of $a(n)$ modulo 2 appears to be entirely different. In particular, we conjecture that, asymptotically, $a(8m+7)$ is odd precisely $50\%$ of the time. This conjecture, whose broad generalization to the context of eta-quotients will be the topic of a subsequent paper, remains wide open., Comment: Minor revisions. To appear in the Int. J. Number Theory

In this paper, we introduce the concept of weak Gabor bi-frame (WGBF) in a general closed subspace [Formula: see text] of [Formula: see text]. It is a generalization of Gabor bi-frame, and is new even if [Formula: see text]. A WGBF for [Formula: see text] contains all information of [Formula: see text] to some extent. Let [Formula: see text], [Formula: see text], and [Formula: see text] be an [Formula: see text]-periodic subset of [Formula: see text] with positive measure. This paper is devoted to characterizing WGBFs for [Formula: see text] of the form [Formula: see text] It is well-known that, if [Formula: see text], the projections of Gabor frames for [Formula: see text] onto [Formula: see text] cannot cover all Gabor frames for [Formula: see text]. This paper presents a Zak transform-domain and a time-domain characterization of WGBFs for [Formula: see text]. These characterizations are new even if [Formula: see text]. Some examples are also provided to illustrate the generality of our theory.

In this paper, we introduce a new graph whose vertices are the non-zero zero-divisors of a commutative ring R, and for distincts elements x and y in the set Z(R)* of the non-zero zero-divisors of R, x and y are adjacent if and only if xy = 0 or x + y ∈ Z(R). We present some properties and examples of this graph, and we study its relationship with the zero-divisor graph and with a subgraph of the total graph of a commutative ring.

International audience; Two finite words [Formula: see text] and [Formula: see text] are [Formula: see text]-binomially equivalent if, for each word [Formula: see text] of length at most [Formula: see text], [Formula: see text] appears the same number of times as a subsequence (i.e., as a scattered subword) of both [Formula: see text] and [Formula: see text]. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the [Formula: see text]-binomial equivalence. We provide an algorithm generating the [Formula: see text]-binomial equivalence class of a word. For [Formula: see text] and alphabet of [Formula: see text] or more symbols, the language made of lexicographically least elements of every [Formula: see text]-binomial equivalence class and the language of singletons, i.e., the words whose [Formula: see text]-binomial equivalence class is restricted to a single element, are shown to be non-context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-[Formula: see text] group (also called free nilpotent group of class [Formula: see text]) on [Formula: see text] generators is isomorphic to the quotient of the free monoid [Formula: see text] by the [Formula: see text]-binomial equivalence.

In this paper we study some products related to quadratic residues and quartic residues modulo primes. Let $p$ be an odd prime and let $A$ be any integer. We mainly determine completely the product $$f_p(A):=\prod_{1\le i,j\le(p-1)/2\atop p\nmid i^2-Aij-j^2}(i^2-Aij-j^2)$$ modulo $p$; for example, if $p\equiv1\pmod4$ then $$f_p(A)\equiv\begin{cases}-(A^2+4)^{(p-1)/4}\pmod p&\text{if}\ (\frac{A^2+4}p)=1, \\(-A^2-4)^{(p-1)/4}\pmod p&\text{if}\ (\frac{A^2+4}p)=-1,\end{cases}$$ where $(\frac{\cdot}p)$ denotes the Legendre symbol. We also determine $$\prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i^2+5ij+2j^2}\left(2i^2+5ij+2j^2\right) \ \text{and}\ \prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i^2-5ij+2j^2}\left(2i^2-5ij+2j^2\right)$$ modulo $p$., 22 pages, final version

In 1851, Prouhet showed that when [Formula: see text] where [Formula: see text] and [Formula: see text] are positive integers, [Formula: see text], the first [Formula: see text] consecutive positive integers can be separated into [Formula: see text] sets, each set containing [Formula: see text] integers, such that the sum of the [Formula: see text]th powers of the members of each set is the same for [Formula: see text]. In this paper, we show that even when [Formula: see text] has the much smaller value [Formula: see text], the first [Formula: see text] consecutive positive integers can be separated into [Formula: see text] sets, each set containing [Formula: see text] integers, such that the integers of each set have equal sums of [Formula: see text]th powers for [Formula: see text]. Moreover, we show that this can be done in at least [Formula: see text] ways. We also show that there are infinitely many other positive integers [Formula: see text] such that the first [Formula: see text] consecutive positive integers can similarly be separated into [Formula: see text] sets of integers, each set containing [Formula: see text] integers, with equal sums of [Formula: see text]th powers for [Formula: see text], with the value of [Formula: see text] depending on the integer [Formula: see text].