Search

It is shown that an approach earlier used by the author for classification of closed simply connected 6-manifolds (reduction to the problem of calculating certain bordism groups) can also be applied for easily obtaining the results by Barden (1965) on classification of closed simply connected 5-manifolds. Bibliography: 11 titles.

Let A be a partition of the segment [0, 1] into a countable number of disjoint subsets of positive measure, let t∈L1(0,1), let Nt be the smallest rearrangement-invariant order ideal vector lattice in L1(0,1), containing t. In the paper one investigates the properties of the image E(Nt¦A) of the averaging operator with respect to A. In particular, one elucidates under what conditions there exists a function g, g∈L1(0,1), such that E(Nt¦A)⊂Ng. One formulates a generalization of the known Hardy-Littlewood inequality, namely Theorem E(t∣A)≺QE(t*∣A*), where ≺ is the Hardy-Littlewood preorder, t* and A* are the decreasing rearrangements of the function ¦t¦ and (in a special sense) of the partition A, while Q is an absolute constant, 1⩽Q⩽25. One formulates the problem of the smallest value of Q.

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

In 1874, Franz Mertens proved the so-called Mertens’ theorem, and in 1974, Kenneth S. Williams showed Mertens’ theorem associated with a character. In a previous paper, we presented a graph-theoretic analogue to Williams’ theorem. In this paper, we generalize our previous work in the sense that a character is extended to a representation. To our knowledge, a number-theoretic analogue to our result is not yet known. So, we expect that, by using our methods, it can be proven in the future.

Let λK m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K p,q -factorization of λK m,n is a set of edge-disjoint K p,q -factors of λK m,n which partition the set of edges of λK m,n . When p = 1 and q is a prime number, Wang, in his paper [On K 1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K 1,q -factorization of K m,n and gave a sufficient condition for such a factorization to exist. In papers [K 1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK m,n to have a K p,q -factorization. As a special case, it is shown that the necessary condition for the K p,q -factorization of λK m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

The study of the global structure of ultrafilters on the natural numbers with respect to the quasi-orders of Rudin-Keisler and Rudin-Blass reducibility was initiated in the 1970s by Blass, Keisler, Kunen, and Rudin. In a 1973 paper Blass studied the special class of P-points under the quasi-ordering of Rudin-Keisler reducibility. He asked what partially ordered sets can be embedded into the P-points when the P-points are equipped with this ordering. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin’s axiom for σ \sigma -centered posets. In his 1973 paper he showed under this assumption that both ω 1 {\omega }_{1} and the reals can be embedded. Analogous results were obtained later for the coarser notion of Tukey reducibility. We prove in this paper that Martin’s axiom for σ \sigma -centered posets implies that the Boolean algebra P ( ω ) / FIN \mathcal {P}(\omega ) / \operatorname {FIN} equipped with its natural partial order can be embedded into the P-points both under Rudin-Keisler and Tukey reducibility. Consequently, the continuum hypothesis implies that every partial order of size at most continuum embeds into the P-points under both notions of reducibility.

This thesis consists of the following papers.I J. Larsson, The Minimum Matching in Pseudo-dimension 0 0.The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.

The present paper is devoted to graph-links with many components and consists of two parts. In the first part of the paper we classify vertices of a labeled graph according to the component they belong to. Using this classification, we construct an invariant of graph-links. This invariant shows that the labeled second Bouchet graph generates a nonrealizable graph-link. In the second part of the work we introduce the notion of an oriented graph-link. We define a writhe number for the oriented graph-link and we get an invariant of oriented graph-links, the Jones polynomial, by normalizing the Kauffman bracket with the writhe number.

The aim of this paper is to present some properties of sT- continuous functions. Moreover, we obtain a characterization and pre- serving theorems of semi-compact, S-closed and s-closed spaces. The study of semi-open sets and semi-continuity in topological spaces was initiated by Levine (10). In 2009, Noiri et al. (13) defined the notion T-open sets and deduced some results. Quite recently, Al-omari et al. (1) have obtained some properties of T-open sets and characterizations of S-closed spaces. In this paper, we present some properties of sT-continuous functions. Moreover, we obtain characterizations and preserving theorems of semi-compact, S-closed and s-closed spaces. 2. Preliminaries Throughout this paper, (X,�) and (Y,�) stand for topological spaces on which no separation axiom is assumed unless otherwise stated. For a subset A of X, the closure of A and the interior of A will be denoted by Cl(A) and Int(A), respectively. Let (X,�) be a space and S a subset of X. A subset S of X is said to be semi-open (10) if there exists an open set U of X such that U ⊆ S ⊆ Cl(U), or equivalently if S ⊆ Cl(Int(S)). The complement of a semi-open set is said to be semi-closed. The intersection of all semi-closed sets containing S is called the semi-closure of S and is denoted by sCl(S). The semi-interior of S, denoted by sInt(S), is defined by the union of all semi-open sets contained in S. It is verified in (2) that sCl(A) = A ∪ Int(Cl(A)) and sInt(A) = A ∩ Cl(Int(A)) for any subset A ⊆ X. A point x ∈ X is said to be in the �-semiclosure of A, denoted by x ∈ �-sCl(A), if A ∩ Cl(V ) 6 � for each semi-open set V containing x. A subset A ⊆ X is said to be �-semiclosed (8) if A = �-sCl(A). The complement of a �-semiclosed set is called a �-semiopen

In this paper we investigate the properties of (a, d)-vertex antimagic total labeling of a digraph D = (V, A). In this labeling, we assign to the vertices and arcs the consecutive integers from 1 to |V|+|A| and calculate the sum of labels at each vertex, i.e., the vertex label added to the labels on its out arcs. These sums form an arithmetical progression with initial term a and common difference d. We show the existence and non-existence of (a, d)-vertex antimagic total labeling for several class of digraphs, and show how to construct labelings for generalized de Bruijn digraphs. We conclude this paper with an open problem suitable for further research.

The aim of this paper is to define the notion of the Cohen- Macaulay cone of a Noetherian local domain R R and to present its applications to the theory of Hilbert-Kunz functions. It has been shown by the second author that with a mild condition on R R , the Grothendieck group G 0 ( R ) ¯ \overline {G_0(R)} of finitely generated R R -modules modulo numerical equivalence is a finitely generated torsion-free abelian group. The Cohen-Macaulay cone of R R is the cone in G 0 ( R ) ¯ R \overline {G_0(R)}_{\mathbb R} spanned by cycles represented by maximal Cohen-Macaulay modules. We study basic properties on the Cohen-Macaulay cone in this paper. As an application, various examples of Hilbert-Kunz functions in the polynomial type will be produced. Precisely, for any given integers ϵ i = 0 , ± 1 \epsilon _i = 0, \pm 1 ( d / 2 > i > d d/2 > i > d ), we shall construct a d d -dimensional Cohen-Macaulay local ring R R (of characteristic p p ) and a maximal primary ideal I I of R R such that the function ℓ R ( R / I [ p n ] ) \ell _R(R/I^{[p^n]}) is a polynomial in p n p^n of degree d d whose coefficient of ( p n ) i (p^n)^i is the product of ϵ i \epsilon _i and a positive rational number for d / 2 > i > d d/2 > i > d . The existence of such ring is proved by using Segre products to construct a Cohen-Macaulay ring such that the Chow group of the ring is of certain simplicity and that test modules exist for it.

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

Let G be a cyclic group of prime power order. There is anatural embedding of Z[G] into a product of rings of integers of cyclotomicfields. In this paper the image of the embedding is determined, and wealso compute the index of the image. 1. IntroductionFor a finite abelian group Glet Z[G] be the integral group ring of G, andlet I G be the augmentation ideal. For each complex character χof Glet Q(χ)be the cyclotomic field generated by the values of χand Z[χ] be its ring ofintegers.ConsiderΦ : Z[G] −→Y χ∈Gb Z[χ]Φ(α) = (...,χ(α),...),where the domain of χis extended to Z[G] by linearity. The map Φ is aninjective ring homomorphism. The goal of this paper is to determine Φ(Z[G])when Gis cyclic of prime power order.For an elementβ= (...,β χ ,...) ∈Y χ∈Gb Z[χ],let us refer to its components β χ as the character values of β. We find that,when Gis cyclic of prime power order, we can express the necessary and suf-ficient condition for β∈ Φ(Z[G]) as congruence relations among the charactervalues of β. As a byproduct, we also compute the index of Φ(Z[G]) inQZ[χ].There are refined type of conjectures on the values of L-functions (cf. [1],[2], [4], [5]) which predict (among others) that certain elements ofQ

Let $X,X_1,\ldots,X_n$ be independent identically distributed random variables. The paper deals with the question about the behavior of the concentration function of the random variable $\sum\limits_{k=1}^{n}X_k a_k$ according to the arithmetic structure of vectors $a_k$. Recently, the interest to this question has increased significantly due to the study of distributions of eigenvalues of random matrices. In this paper we formulate and prove multidimensional generalizations of the results Eliseeva and Zaitsev (2012). They are also the refinements of the results of Friedland and Sodin (2007) and Rudelson and Vershynin (2009)., Comment: 13 pages

In this paper, we investigate the uniqueness problem on entire functionssharing fixed points (ignoring multiplicities). Our main results improve and generalizesome results due to Zhang [13], Qi-Yang [10] and Dou-Qi-Yang [1]. 1. IntroductionIn this paper, a meromorphic function will mean meromorphic in the wholecomplex plane. We assume that the reader is familiar with standard notations andfundamental results of Nevanlinna Theory as explained in [12].We say that two meromorphic functions f and g share a small function a(z) IM(ignoring multiplicities) when f −a and g−a have the same zeros. If f and g havethe same zeros with the same multiplicities, then we say that f and g share a(z)CM (counting multiplicities).Let p be a positive integer and a ∈ C. We denote by N p (r, 1f−a ) the countingfunction of the zeros of f − a where an m-fold zero is counted m times if m ≤ pand p times if m > p. We denote by N L (r, 1f−1 ) the counting function for 1-pointsof both f(z) and g(z) about which f(z) has a larger multiplicity than g(z), withmultiplicity not being counted. We say that a finite value z

This paper discusses the asymptotic behaviors of the longest run on a countable state Markov chain. Let \(\left\{ {X_a } \right\}_{a \in Z_ + }\) be a stationary strongly ergodic reversible Markov chain on countablestate space S = {1, 2, ...}. Let T ⊂ S be an arbitrary finite subset of S. Denote by L n the length of the longest run of consecutive i’s for i ∈ T, that occurs in the sequence X 1, ..., X n . In this paper, we obtain a limit law and a week version of an Erdos-Renyi type law for L n . A large deviation result of L n is also discussed.

In a paper by Z. Lu and J. Rowlett, it is shown that the eigenvalues of the weighted Laplacian can be approximated by eigenvalues of a naturally associated family of narrow graphs. In this paper, we generalize this result to the p p -Laplacian. Our approach features overcoming the nonlinearity of the p p -Laplacian when p ≠ 2 p\neq 2 , which is different from the Laplacian case.

The subject of this paper is to give the description, up to topological conjugacy, of possible minimal sets of triangular maps of the square of type 2 ∞ . In [4] , we give a general method allowing to embed any zero-dimensional almost 1–1 extension of the dyadic odometer (in particular any dyadic Toeplitz system) as a minimal set of a triangular map of this type. In this paper we present a method (a combination of that described in [4] with one introduced in [1] ) of similarly embedding a special class of zero-dimensional almost 2–1 extensions of the odometer. We conjecture that these two embedding theorems exhaust all possibilities for nonperiodic minimal sets. The paper was inspired by the last unsolved problem in the Sharkovski classification program of triangular maps: does there exist a triangular map with positive entropy attained on the set of uniformly recurrent points but with entropy zero on the set of regularly recurrent points. The paper answers this question positively, concluding the program.

In an earlier paper (arxiv:1108.4292) we introduced a new concept of dimension for metric spaces, the so called topological Hausdorff dimension. For a compact metric space $K$ let $\dim_{H}K$ and $\dim_{tH} K$ denote its Hausdorff and topological Hausdorff dimension, respectively. We proved that this new dimension describes the Hausdorff dimension of the level sets of the generic continuous function on $K$, namely $\sup{\dim_{H}f^{-1}(y) : y \in \mathbb{R}} = \dim_{tH} K - 1$ for the generic $f \in C(K)$, provided that $K$ is not totally disconnected, otherwise every non-empty level set is a singleton. We also proved that if $K$ is not totally disconnected and sufficiently homogeneous then $\dim_{H}f^{-1}(y) = \dim_{tH} K - 1$ for the generic $f \in C(K)$ and the generic $y \in f(K)$. The most important goal of this paper is to make these theorems more precise. As for the first result, we prove that the supremum is actually attained on the left hand side of the first equation above, and also show that there may only be a unique level set of maximal Hausdorff dimension. As for the second result, we characterize those compact metric spaces for which for the generic $f\in C(K)$ and the generic $y\in f(K)$ we have $\dim_{H} f^{-1}(y)=\dim_{tH}K-1$. We also generalize a result of B. Kirchheim by showing that if $K$ is self-similar then for the generic $f\in C(K)$ for every $y\in \inter f(K)$ we have $\dim_{H} f^{-1}(y)=\dim_{tH}K-1$. Finally, we prove that the graph of the generic $f\in C(K)$ has the same Hausdorff and topological Hausdorff dimension as $K$., 20 pages

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

Let G =(V,E)beagraphwithchromaticnumber χ(G). Adominating set D of G is called a chromatic transversal dominating set(ctd-set) if D intersects every color class of every χ-partitionof G. Theminimumcardinalityofactd-setofG iscalledthechromatictransversaldomination number of G and is denoted by γ ct (G). In this paper wecharacterizetheclassoftrees,unicyclicgraphsandcubicgraphsforwhichthe chromatic transversal domination number is equal to the connecteddominationnumber. 1. IntroductionAll the graphs considered in this paper unless otherwise specifically statedare finite, connected and simple and are consistent with the terminology usedin Harary [4]. Let G = (V,E) be a simple graph of order p. For a subset Sof V, N(S) denotes the set of all vertices adjacent to some vertex in S andN[S] = N(S) ∪S.A vertex v of G is called a support if it is adjacent to a pendant vertex. Anyvertex of degree greater than one is called an internal vertex. A graph G iscalled a unicyclic graph, if G contains exactly one cycle.A subset D ⊆ V is a dominating set, if every v ∈ V − D is adjacent tosome u ∈ D. The domination number γ = γ(G) is the minimum cardinality ofa dominating set of G. A dominating set D is called a connected dominatingset if the induced subgraph hDi is connected. The minimum cardinality of aconnected dominating set is called the connected domination number and isdenoted by γ

In this paper, for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs, a novel eccentricity-based invariant, named as non-self-centrality number (NSC number for short), of a graph G is defined as follows: \(N\left( G \right) = \sum\nolimits_{{v_i}{v_j} \in V\left( G \right)} {|{e_i} - {e_j}|} \) where the summation goes over all the unordered pairs of vertices in G and ei is the eccentricity of vertex vi in G, whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G. In this paper, we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained. Finally we propose some attractive research topics for this new invariant of graphs.

In this paper we discuss a problem of generalization of binomial distributed triangle, that is sequence A287326 in OEIS. The main property of A287326 that it returns a perfect cube n as sum of n-th row terms over k, 0 or 1 , by means of its symmetry. In this paper we have derived a similar triangles in order to receive powers m=5,7 as row items sum and generalized obtained results in order to receive every odd-powered monomial n2m+1, m as sum of row terms of corresponding triangle. This version might be out of date, proceed by the link to see actual version., 16 pages, 8 figures, 2 tables, typos revised, added missing references, results generalized and shortened, derivations detailed.

In this paper we introduce the notion of P-strongly regu-lar near-ring. We have shown that a zero-symmetric near-ring N is P-strongly regular if and only if N is P-regular and P is a completelysemiprime ideal. We have also shown that in a P-strongly regular near-ring N, the following holds: (i) Na+ P is an ideal of N for any a∈N.(ii) Every P-prime ideal of N containing P is maximal. (iii) Every idealI of N fulfills I+ P = I 2 + P. 1. IntroductionThroughout this paper, N denotes a zero-symmetric right near-ring. Aright N-subgroup (left N-subgroup) of N is a subgroup I of (N,+) such thatIN ⊆ I(NI ⊆ I). A quasi-ideal of N is a subgroup Q of (N,+) such thatQN ∩ NQ ⊆ Q. Right N-subgroups and left N-subgroups are quasi-ideals.The intersection of a family of quasi-ideals is again a quasi-ideal.Nis called regular, if for every element aof Nthere exists an element x∈ Nsuch that a= axa. Let P be an ideal of N. Then the near-ring N is said tobe a P-regular near-ring if for each a ∈ N, there exists an element x ∈ Nsuch that a= axa+ p for some p∈ P. If P = 0, then a P-regular near-ringis a regular near-ring. Here the notion of P-regularity is a generalization ofregularity. There are near-rings which are P-regular but not regular.V. A. Andrunakievich [1] defined P-regular rings and S. J. Choi [3] extendedthe P-regularity of a ring to the P-regularity of a near-ring. In this paper weintroduce the notion of P-strongly regular near-ring and obtain equivalent con-ditions for a near-ring to be P-strongly regular. We also introduce the notionsof P-prime ideals and P-near-ring in this paper. I. Yakabe [7] characterizedregular zero-symmetricnear-rings without non-zero nilpotent elements in termsof quasi-ideals. In this paper we characterize P-strongly regular near-ring interms of quasi-ideals. For the basic terminology and notation we refer to [6].

The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + mp ≤ D(Gn) ≤ n + mp + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and mp depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(Gn) = n + mp (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m - n ≫ n2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian, or Q-matrix. In our previous paper [1] we gave three lower and three upper bounds for the Q-index of nested split graphs, also known as threshold graphs. In this paper, we give another two upper bounds, which are expressed as solutions of cubic equations (in contrast to quadratics from [1]). Some computational results are also included.

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be \(O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)\). This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided.

In this paper we shall present discrete Kolmogorov type inequalities for multiply monotone sequences defined on non-positive integers. Moreover, we will provide a more delicate information by obtaining the description of the following modulus of continuity ω j,r p,q (δ ,e) = sup{‖∆ x‖q : x,∆x, . . . ,∆ j x ! 0, ‖x‖p = δ , ‖∆ x‖∞ = e} for δ ! e > 0 and values of j = r−2 or j = r−1 depending on values of other parameters. 1. Notation, definitions, and history Let M := Z− ∪ {0} = {· · · ,−2,−1,0} . We shall define the (forward) difference operator as follows: for the sequence x = {xm}m∈M set ∆x := {xm − xm−1}m∈M, ∆x := x, ∆x := ∆x, and, recursively, ∆ x := ∆(∆ )x for j = 2,3, . . . . Let lp = lp(M) , p ∈ [1,∞] , be the space of all real-valued sequences defined on M such that the norm ‖x‖p :=    ( ∑ m∈M |xm| p )1/p , 1 " p < ∞, sup m∈M |xm|, p = ∞, is finite. Note that in contrast with the derivative operator D = d dt , the difference operator ∆ is a bounded linear operator defined on all lp(M) for any 1 " p " ∞ . In this paper we shall consider sharp discrete inequalities of Kolmogorov type, i.e. inequalities of the form ‖∆x‖q "C‖x‖ α p‖∆ x‖ s , x ∈ lp(U), ∆ x ∈ ls(U) (1) where U = M or U = Z and α ∈ [0,1] is defined by relation (9) below. The exact constants C = C(k,r, p,q,s) in inequalities of this form have been found in the following cases: Mathematics subject classification (2010): 26D10, 47B39, 39A70, 65L12.

There has been an emerging interest in developing an approximation theory for manifold-valued functions. In this paper, we address the following fundamental problem: Let M be a manifold with a metric d. For each smoothness factor r > 0 and approximation order R > 0, is there an approximation operator Ah = Ah;r,R that maps samples of any f : R→ M on a grid of size h to an approximant fh = Ah(f |hZ) : R→ M with the properties that a) supx d(fh(x), f(x)) = O(h) whenever f is a bounded C function, and b) fh is C smooth ? The case of M = R is of course well-studied. In the recent paper [14], the authors show that subdivision methods can be used to create arbitrarily smooth interpolants for M -valued data, addressing b) above. In this paper we further show that interpolatory subdivision schemes can be used to solve a) above. So, altogether, we establish the fact that if a linear interpolatory subdivision scheme possesses a smoothness order r and an approximation order R, then a nonlinear interpolatroy subdivision scheme for M -valued data constructed based on this linear scheme has the same smoothness and approximation orders. In other words, subdivision schemes furnish a constructive approximation method for solving the open problem posted above. We discuss the construction of quasi-interpolants of manifold-valued data based on general (not necessarily interpolatory) subdivision schemes. Acknowledgments. The work of this research was partially supported by the National Science Foundation grant DMS 0542237. The empirical observation on approximation equivalence (Figure 1) was first presented in the Sixth International Conference on Curves and Surfaces (Avignon, France, June 29-July 5, 2006.) and further discussed in a mini-symposium in the 12th International Conference in Approximation Theory (San Antonio, Texas, March 4-8, 2007) and the MAIA 2007 conference (Alesund, Norway, August 22-26, 2007.) A preliminary effort on this problem was made in [5]. The second named author thanks Nira Dyn for inviting him to a workshop on “Subdivision and Refinability” (Pontignano, Siena, Italy, May 1-4, 2008), at which the main result of this paper was first presented.

In this paper we present a probabilistic construction of countable abelian p p -groups with prescribed Ulm-sequence. This result provides a different proof for the existence theorem of abelian p p -groups with any given countable Ulm-sequence due to Ulm, which is sometimes called Zippin’s theorem. The basic idea, applying probabilistic arguments, comes from a result by Erdős and Rényi. They gave an amazing probabilistic construction of countable graphs which, with probability 1 1 , produces the universal homogeneous graph, therefore also called the random graph. P. J. Cameron says about this in his book Oligomorphic Permutation Groups [Cambridge University Press, 1990]: In 1963, Erdős and Rényi proved the following paradoxical result. … It is my contention that mathematics is unique among academic pursuits in that such an apparently outrageous claim can be made completely convincing by a short argument. The algebraic tool in the present paper needs methods developed in the 1970s, the theory of valuated abelian p p -groups. Valuated abelian p p -groups are natural generalizations of abelian p p -groups with the height valuation, investigated in detail by F. Richman and E. Walker, and others. We have to establish extensions of finite valuated abelian p p -groups dominated by a given Ulm-sequence. Probabilistic results of a similar nature have been established by A. Blass and G. Braun, and by M. Droste and D. Kuske.

The pattern complexity of a word for a given pattern S, where S is a finite subset of {0,1,2,…}, is the number of distinct restrictions of the word to S+n (with n=0,1,2,…). The maximal pattern complexity of the word, introduced in the paper of T. Kamae and L. Zamboni [Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Th. & Dynam. Sys.22(4) (2002), 1191–1199], is the maximum value of the pattern complexity of S with #S=k as a function of k=1,2,…. A substitution of constant length on an alphabet is a mapping from the alphabet to finite words on it of constant length not less than two. An infinite word is called a fixed point of the substitution if it stays the same after the substitution is applied. In this paper, we prove that the maximal pattern complexity of a fixed point of a substitution of constant length on {0,1} (as a function of k=1,2,…) is either bounded, a linear function of k, or 2k.

This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value mk(n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains k vertices of each color. In this paper, we obtain the exact values of m2(5) and m2(4), and the upper bounds for m3(7) and m4(9).

In this paper, we consider structured automata without output signals whose state sets are endowed with an algebraic structure of hypergraphs. The main result of the paper is a theorem where we obtain necessary and sufficient conditions for the possibility of defining on the state set of some automaton A a structure of a hypergraph H such that the automaton A will be the universal hypergraphic automaton.

Let $$f : {\mathbb{R}} \longrightarrow {\mathbb{R}}$$ denote the function given by $$f(t) = \sum \limits^{\infty}_{n=0} a_{n}t^{n}, t \in {\mathbb{R}}$$ , where $$a_n \geq 0, n \in {\mathbb{N}}$$ . Let K be a closed convex cone in a real Banach space and $$H : K \longrightarrow cc(K)$$ a linear and continuous set-valued function with nonempty, convex and compact values in K. The set-valued function $$F^t(x) := \sum \limits_{n=0}^{\infty} a_{n}t^{n}H^{n}(x), x \in K$$ is linear and continuous for all $$t \geq 0$$ and $$F^{t} \circ F^{s}(x) \subseteq \sum \limits_{n=0}^{\infty} c_{n}H^{n} (x), x \in K$$ where $$c_{n} = \sum \limits_{k=0}^{n} a_{k} a_{n-k}{{t^{k}}s^{n-k}}, t, s \geq 0$$ . The paper generalizes papers of J. Plewnia and M. Piszczek where f is an exponential and a cosine function respectively.

In this paper, one kind of subgroup in arbitrary group which similar to the linear subspace was constructed, and the generalization of the Hahn-Banach theorem on this kind of subgroup in arbitrary groups was obtained. The Hahn-Banach theorem is a powerful existence theorem whose form is par- ticularly appropriate to applications in linear problems. In its elegance and power, the Hahn-Banach theorem is a favorite of almost every analyst. The generalization of the Hahn-Banach theorem on groups has been discussed in many articles, much of these discussions were under the assumption of some condition of groups, such as the weakly commutativity in the paper of Z. Gajda and Z. Kominek (3), or groups in class G during R. Badora (1). The purpose of this paper is to find the sucient and necessary condition of Hahn-Banach theorem on arbitrary groups. Let G be a group, p,f be functionals on G ! R, then p is subadditive and f is additive if and only if p(xy) p(x) + p(y), x,y 2 G and f(xy) = f(x) + f(y), x,y 2 G. Moreover, p is completely commutative if and only if for any n 2 Z + and any per- mutation xk1,··· ,xkn of x1,··· ,xn 2 G, one has p( n Y i=1 xi) = p( n Y i=1 xki ).

Let N be a zero-symmetric near-ring with identity and let Γ(N) be a graphwith vertices as elements of N, where two different vertices a and b are adjacent if and onlyif hai + hbi = N, where hxi is the ideal of N generated by x. Let Γ 1 (N) be the subgraphof Γ(N) generated by the set {n ∈ N : hni = N} and Γ 2 (N) be the subgraph of Γ(N)generated by the set N\v(Γ 1 (N)), where v(G) is the set of all vertices of a graph G. Inthis paper, we completely characterize the diameter of the subgraph Γ 2 (N) of Γ(N). Inaddition, it is shown that for any near-ring, Γ 2 (N)\M(N) is a complete bipartite graph ifand only if the number of maximal ideals of N is 2, where M(N) is the intersection of allmaximal ideals of N and Γ 2 (N)\M(N) is the graph obtained by removing the elements ofthe set M(N) from the vertices set of the graph Γ 2 (N). 1. PreliminariesThroughout this paper N is a zero symmetric near-ring with identity. M(N)denotes the intersection of all maximal ideals of N, Max(N) denotes the set of allmaximal ideals of N, hxi denotes the ideal of N generated by x and v(G) denotesthe set of all vertices of a graph G.For any vertices x,y in a graph G, if x and y are adjacent, we denote it as x ≈ y.A graph is said to be connected if for each pair of distinct vertices v and w, thereis a finite sequence of distinct vertices v

In this paper we pursue and deep the study of ring extensions \({R \subset S}\) such that R is a maximal non-valuation subring of S [Ben Nasr and Jarboui in Houston J Math, 2009 (in press)]. It is proved in Ben Nasr and Jarboui [Houston J Math, 2009 (in press), Theorem 3.2] that if R is integrally closed with finite Krull dimension, then R is a maximal non-valuation subring of qf (R) iff R is not local and |[R, qf (R)]| = dim(R) + 3. This result encourages us to pose the following question: Let n be a nonzero positive integer greater than 2 and let R be a finite-dimensional domain such that |[R, qf (R)]| = dim(R) + n, does there exists an overring S of R such that R is a maximal non-valuation subring of S? This paper deals mostly with this question. We solve this question in case R is integrally closed.

This paper is a follow-up to a previous paper where the logical characterization of n-ary synchronous relations due to Eilenbeig, Elgot, and Shepherdson was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicates leads to a completely different picture for infinite alphabets, though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the Σ2 fragment. Finally, we show that the existential fragment is decidable. Bibliography: 19 titles.

In the papers [5]-[7] was examined approximation of functions by the modi edSz asz-Mrakyan operators and other positive linear operators preserving e 2 (x) = x 2 : In thispaper we introduce the Post-Widder and Stancu operators preserving x 2 in polynomialweighted spaces. We show that these operators have better approximation properties thanclassical Post-Widder and Stancu operators. 1. Introduction1.1. The Post-Widder operators(1) P n (f;x) P n (f(t);x) :=Z 10 f(t)p n (x;t)dt; x 2I; n 2N;(2) p n (x;t) :=(n=x) n t n 1 (n 1)!exp ntx ;I = (0;1), N = f1;2;g , were examined in many papers and monographs (e.g.[4]) for real-valued functions f bounded on I. It is known ([4], Chapter 9) that P n are well de ned also for functions e k (x) = x k , k 2N 0 = N [f0g, and(3) P n (e 0 ;x) = 1; P n (e 1 ;x) = x; P n (e 2 ;x) =n+ 1nx 2 and generally(4) P n (e k ;x) =n(n+ 1) (n+ k k1)xn k ; k 2N; Corresponding author.Received 19 June 2007; accepted 23 October 2007.2000 Mathematics Subject Classi cation: 41A25, 41A36.Key words and phrases: Post-Widder operator, Stancu operator, polynomial weightedspace, approximation theorem.

A partial order on the set of the prime knots can be defined by the existence of a surjective homomorphism between knot groups. In the previous paper, we determined the partial order in the knot table. In this paper, we prove that 31 and 41 are minimal elements. Further, we study which surjection a pair of a periodic knot and its quotient knot induces, and which surjection a degree one map can induce.

Let A be a class of Abelian groups, A ∈ A, and End(A) be the additive endomorphism group of the group A. The group A is said to be defined by its endomorphism group in the class {ie208-01} if for every group B ∈ B such that End(B) ≅ End(A) the isomorphism B ≅ A holds. The paper considers the problem of definability of a periodic Abelian group A such that End-End(A) ≅ End(A). The classes of periodical Abelian groups, of divisible Abelian groups, of reduced Abelian groups, of nonreduced Abelian groups, and of all Abelian groups are investigated in this paper.

For a nonnegative real matrix A of rank 1, A can be factored as ab t for somevectors a and b. The perimeter of A is the number of nonzero entries in both a and b. If Bis a matrix of rank k, then B is the sum of k matrices of rank 1. The perimeter of B is theminimum of the sums of perimeters of k matrices of rank 1, where the minimum is takenover all possible rank-1 decompositions of B. In this paper, we obtain characterizations ofthe linear operators which preserve perimeters 2 and k for some k ≥ 4. That is, a linearoperator T preserves perimeters 2 and k(≥ 4) if and only if it has the form T(A) = UAV ,or T(A) = UA t V with some invertible matrices U and V . 1. IntroductionThere is much literature on the study of linear operators that preserve theranks of matrices over several semirings([1]-[8]). Nonnegative matrices also havebeen the subject of research by many authors([2], [5], [6], [8]). Beasley, Gregoryand Pullman [2] obtained characterizations of linear operators which preserve therank of nonnegative real matrices. In [8], Song and Hwang characterized spanningcolumn ranks and their preservers of nonnegative matrices. Beasley, Song, Kangand Sarma [5] treated column ranks of nonnegative real matrices and characterizedtheir preservers.But there are few papers on the characterizations of linear operators preserv-ing the perimeter of matrices. Beasley et al. characterized those linear operatorspreserving the rank and perimeter of Boolean rank-1 matrices([1]).In this paper, we consider the set of linear operators that preserve the perimeterof matrices of rank k(≥ 2) over the nonnegative reals.

In this paper, we deal with the problem of meromorphic functions that havethree weighted sharing values, and obtain some uniqueness theorems which improve thosegiven by N. Terglane, Hong-Xun Yi & Xiao-Min Li, and others. Some examples are pro-vided to show that the results in this paper are best possible. 1. Introduction and main resultsIn this paper, by meromorphic functions we will always mean meromorphicfunctions in the complex plane. We adopt the standard notations in the Nevan-linna theory of meromorphic functions as explained in [3]. It will be convenient tolet E denote any set of positive real numbers of finite linear measure, not necessarilythe same at each occurrence. For any nonconstant meromorphic function h(z), wedenote by S(r,h) any quantity satisfying S(r,h) = o(T(r,h)) (r → ∞,r 6∈E).Let f(z) and g(z) be two nonconstant meromorphic functions, and let a ∈C ∪ {∞}, where C ∪ {∞} denotes the extended complex plane. We denote byN 0 (r,a,f,g) the counting function of the common zeros of f(z) − a and g(z) − a,and each point is counted only once, where f(z)−∞ means 1/f(z) (see [10]). We saythat f and g share the value a CM, provided that f and g have the same a−pointswith the same multiplicities. Similarly, we say that f and g share the value a IM,provided that f and g have the same a−points ignoring multiplicities (see [12]).Throughout this paper, we denote by N

For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of G, is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 33 vertices) defining an NP-complete CSP(G).

Plesnik in 1972 proved that an (m − 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m − 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤ n/2. In particular, we generalize Plesnik’s result and the results obtained by Liu et al. in 1998, and improve Katerinis’ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.

It is well known that there are no nonzero linear derivations on complex commutative semisimple Banach algebras. In this paper we prove the following extension of this result. Let A be a complex semisimple Banach algebra and let D : A → A be a linear mapping satisfying the relation D(x 2) = 2xD(x) for all x ∈ R. In this case D = 0. Throughout, R will represent an associative ring with center Z(R). A ring R is n-torsion free, where n > 1 is an integer, if nx = 0, x ∈ R implies x = 0. As usual the commutator xy − yx will be denoted by [x, y]. We shall use the commutator identities [xy, z] = [x, z] y + x [y, z] and [x, yz] = [x, y] z + y [x, z] for all x, y, z ∈ R. Recall that a ring R is prime if for a, b ∈ R, aRb = (0) implies that either a = 0 or b = 0, and is semiprime in case aRa = (0) implies that a = 0. An additive mapping D is called a derivation if D(xy) = D(x)y + xD(y) holds for all pairs x, y ∈ R, and is called a Jordan derivation in case D(x 2) = D(x)x + xD(x) is fulfilled for all x ∈ R. Obviously, any derivation is a Jordan derivation. The converse is in general not true. Herstein ([8]) has proved that any Jordan derivation on a 2-torsion free prime ring is a derivation (see also [1]). Cusack ([5]) has generalized Herstein’s result to 2-torsion free semiprime rings (see [2] for an alternative proof). An additive mapping D : R → R is called a left derivation if D(xy) = yD(x) + xD(y) holds for all pairs x, y ∈ R and is called a left Jordan derivation (or Jordan left derivation) in case D(x 2) = 2xD(x) is fulfilled for all x ∈ R. In this paper by a Banach algebra we mean a Banach algebra over the complex field.

In 1945 Duffin and Schaeffer proved that a power series that is bounded in a sector and has coefficients from a finite subset of C is already a rational function. Their proof is relatively indirect. It is one purpose of this paper to give a shorter direct proof of this beautiful and surprising theorem. This will allow us to give an easy proof of a recent result of two of the authors stating that a sequence of polynomials with coefficients from a finite subset of C cannot tend to zero uniformly on an arc of the unit circle. Another main result of this paper gives explicit estimates for the number and location of zeros of polynomials with bounded coefficients. Let n be so large that v satisfies δn≤ 1. We show that any polynomial in has at least zeros in any disk with center on the unit circle and radius αn.