Search

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, 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.

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).

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following: A classical result of Lipton, Rose and Tarjan from 1979 states that if F is a hereditary family of graphs and every graph in F has a vertex separator of size n/(log⁡n)1+o(1), then every graph in F has O(n) edges. We construct a hereditary family of graphs with vertex separators of size n/(log⁡n)1−o(1) such that not all graphs in the family have O(n) edges. Trevisan and Arora-Barak-Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G's edges. Sudakov and the second author have recently shown that every graph with average degree d contains an n-vertex subgraph with average degree at least (1−o(1))d and vertex expansion 1/(log⁡n)1+o(1). We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1). The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super-linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.

We analyze a new random algorithm for numerical integration of d -variate functions over [ 0 , 1 ] d from a weighted Sobolev space with dominating mixed smoothness α ≥ 0 and product weights 1 ≥ γ 1 ≥ γ 2 ≥ ⋯ > 0 , where the functions are continuous and periodic when α > 1 ∕ 2 . The algorithm is based on rank-1 lattice rules with a random number of points n . For the case α > 1 ∕ 2 , we prove that the algorithm achieves almost the optimal order of convergence of O ( n − α − 1 ∕ 2 ) , where the implied constant is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 ∕ α ∞ . The same rate of convergence holds for the more general case α > 0 by adding a random shift to the lattice rule with random n . This shows, in particular, that the exponent of strong tractability in the randomized setting equals 1 ∕ ( α + 1 ∕ 2 ) , if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov’s method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-1 lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors.

The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here – size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees – justifies our interests in this Acknowledgement : The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).

In this paper we investigate a special sequence related to the Halton sequence, namely the Halton sequence indexed by ⌊ n β ⌋ with β ∈ R , and prove a metric almost low-discrepancy result.

Gy\'arf\'as, Gy\H{o}ri and Simonovits proved that if a $3$-uniform hypergraph with $n$ vertices has no linear cycles, then its independence number $\alpha \ge \frac{2n} {5}$. The hypergraph consisting of vertex disjoint copies of a complete hypergraph $K_5^3$ on five vertices, shows that equality can hold. They asked whether this bound can be improved if we exclude $K_5^3$ as a subhypergraph and whether such a hypergraph is $2$-colorable. In this paper we answer these questions affirmatively. Namely, we prove that if a $3$-uniform linear-cycle-free hypergraph doesn't contain $K_5^3$ as a subhypergraph, then it is $2$-colorable. This result clearly implies that its independence number $\alpha \ge \lceil \frac{n}{2} \rceil$. We show that this bound is sharp. Gy\'arf\'as, Gy\H{o}ri and Simonovits also proved that a linear-cycle-free $3$-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free $3$-uniform hypergraph has a vertex of degree at most $n-2$ when $n \ge 10$., Comment: Improved the writing, more explanation added and corrections made

The Paul Erdős and Andras Gyarfas conjecture states that every graph of minimum degree at least 3 contains a simple cycle whose length is a power of two. In this paper, we prove that the conjecture holds for Cayley graphs on generalized quaternion groups, dihedral groups, semidihedral groups and groups of order \(p^3\).

Consider the random graph G(Pn,r) whose vertex set Pn is a Poisson point process of intensity n on (-12,12]d,d2. Any two vertices Xi,XjPn are connected by an edge with probability g(d(Xi,Xj)r), independently of all other edges, and independent of the other points of Pn. d is the toroidal metric, r > 0 and g:0,)0,1] is non-increasing and =dg(|x|)dx ) does not have any isolated nodes satisfies lim?nnMndlog?n=1. Let =inf?{x > 0:xg(x)> 1}, and be the volume of the unit ball in d. Then for all >, G(Pn,(log?nn)1d) is connected with probability approaching one as n. The bound can be seen to be tight for the usual random geometric graph obtained by setting g=10,1]. We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy g(r)=o(r-c).

Let G = (V,E) be a simple graph. A function f: E → {+1,−1} is called a signed cycle domination function (SCDF) of G if Ʃ e∈E(C) f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc(G) = min{Ʃ e∈E f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ′sc(G) = n.

Let G be a finite group and σ = {σ i |i∈I} be a partition of the set of all primes P. A set H of subgroups of G is said to be a complete Hall σ-set of G if every non-identity member of H is a Hall σ i -subgroup of G and H contains exactly one Hall σ i -subgroup of G for every σ i ∈ σ(G). A subgroup H is said to be σ-permutable if G possesses a complete Hall σ-set H such that HA x = A x H for all A ∈ H and all x ∈ G. Let H be a subgroup of G. Then we say that: (1) H is σ-embedded in G if there exists a σ-permutable subgroup T of G such that HT = H σG and H ∩ T ≤ H σG , where H σG is the subgroup of H generated by all those subgroups of H which are σ-permutable in G, and H σG is the σ-permutable closure of H, that is, the intersection of all σ-permutable subgroups of G containing H. (2) H is σ-n-embedded in G if there exists a normal subgroup T of G such that HT = H G and H ∩ T ≤ H σG . In this paper, we study the properties of the new embedding subgroups and use them to determine the structure of finite groups.

This paper studies the distribution of a family of rankings, which includes Google's PageRank, on a directed configuration model. In particular, it is shown that the distribution of the rank of a randomly chosen node in the graph converges in distribution to a finite random variable R* that can be written as a linear combination of i.i.d. copies of the attracting endogenous solution to a stochastic fixed-point equation of the form R=D∑i=1NCiRi+Q, where (Q,N,{Ci}) is a real-valued vector with N∈{0,1,2,…}, P(|Q|>0)>0, and the {Ri} are i.i.d. copies of R, independent of (Q,N,{Ci}). Moreover, we provide precise asymptotics for the limit R*, which when the in-degree distribution in the directed configuration model has a power law imply a power law distribution for R* with the same exponent. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 2017

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.

Let $G=(V,E)$ be a finite and simple graph of order $n$ and maximum degree $\Delta$. A signed strong Roman dominating function (abbreviated SStRDF) on a graph $G$ is a function $f:V\to \{-1,1,2,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}$ satisfying the conditions that (i) for every vertex $v$ of $G$, $\sum_{u\in N[v]} f(u)\ge 1$, where $N[v]$ is the closed neighborhood of $v$ and (ii) every vertex $v$ for which $f(v)=-1$ is adjacent to at least one vertex $u$ for which $f(u)\ge 1+\lceil\frac{1}{2}|N(u)\cap V_{-1}|\rceil$, where $V_{-1}=\{v\in V \mid f(v)=-1\}$. The minimum of the values $\sum_{v\in V} f(v)$, taken over all signed strong Roman dominating functions $f$ of $G$, is called the signed strong Roman domination number of $G$ and is denoted by $\gamma_{ssR}(G)$. In this paper we initiate the study of the signed strong Roman domination in graphs and present some (sharp) bounds for this parameter.

Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′∑(G). Flandrin et al. proposed the following conjecture that χ′∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < $$\tfrac{{37}} {{12}}$$ and Δ(G) ≥ 7.

In this paper we study trigonometric series with general monotone coefficients, i.e., satisfying $$\begin{aligned} \sum \limits _{k=n}^{2n} |a_k - a_{k+1}| \le C \sum \limits _{k=[{n}/{\gamma }]}^{[\gamma n]} \frac{|a_k|}{k}, \quad n\in \mathbb {N}, \end{aligned}$$ for some $$C \ge 1$$ and $$\gamma >1$$ . We first prove the Lebesgue-type inequalities for such series $$\begin{aligned} n|a_n|\le C \omega (f,1/n). \end{aligned}$$ Moreover, we obtain necessary and sufficient conditions for the sum of such series to belong to the generalized Lipschitz, Nikolskii, and Zygmund spaces. We also prove similar results for trigonometric series with weak monotone coefficients, i.e., satisfying $$\begin{aligned} |a_n | \le C \sum \limits _{k=[{n}/{\gamma }]}^{\infty } \frac{|a_k|}{k}, \quad n\in \mathbb {N}, \end{aligned}$$ for some $$C \ge 1$$ and $$\gamma >1$$ . Sharpness of the obtained results is given. Finally, we study the asymptotic results of Salem–Hardy type.

The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora etal. (Arora etal., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition.We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models.

Let A be an integral domain, $$S\subseteq A$$ be a multiplicative set and M a w-module as an A-module. In this paper we investigate S-SM-modules. We give an S-version of the result of Wang and McCasland (Commun Algebra 25:1285–1306, 1997) in the case where S is countable. We prove that M is an S-SM-module if and only if every increasing sequence of w-submodules of M is S-stationary if and only if every increasing sequence of S-w-finite w-submodules of M is S-stationary if and only if every increasing sequence of w-finite type submodules of M is S-stationary.

This paper delves into the number of partitions of positive integers n into powers of 2 in which exactly m powers of 2 are used an odd number of times. The study of these numbers is motivated by their connections with the f-vectors of the binary partition polytopes.

In polynomial regression modeling, the use of a second order orthogonal Latin hypercube design guarantees that the estimates of the first order effects are uncorrelated to each other as well as to the estimates of the second order effects. In this paper, we prove that such designs with n runs and k>2 columns do not exist if n4mod8. Furthermore, we prove that second order Latin hypercube designs with k4 columns that guarantee the orthogonality of two-factor interactions which do not share a common factor, do not exist for even n that is not a multiple of 16. Finally, we investigate the class of symmetric orthogonal Latin hypercube designs (SOLHD), which are a special subset of second order orthogonal Latin hypercube designs. We describe construction techniques for SOLHDs with n runs and (a) k4 columns, when n0mod8 or n1mod8, (b) k8 columns when n0mod16 or n1mod16 and (c) k=4 columns when n0mod16 or n1mod16, that guarantee the orthogonality of two-factor interactions which do not share a common factor. Finally, we construct and enumerate all non-isomorphic SOLHDs with n17 runs and k2 columns, as well as with 19n20 runs and k=2 columns.

Let S = (a 1, …, a m ; b 1, …, b n ), where a 1, …, a m and b 1, …, b n are two nonincreasing sequences of nonnegative integers. The pair S = (a 1, …, a m ; b 1, …, b n ) is said to be a bigraphic pair if there is a simple bipartite graph G = (X ∪ Y, E) such that a 1, …, a m and b 1, …, b n are the degrees of the vertices in X and Y, respectively. Let Z 3 be the cyclic group of order 3. Define σ(Z 3, m, n) to be the minimum integer k such that every bigraphic pair S = (a 1, …, a m ; b 1, …, b n ) with a m , b n ≥ 2 and σ(S) = a 1 + ⋯ + a m ≥ k has a Z 3-connected realization. For n = m, Yin [Discrete Math., 339, 2018—2026 (2016)] recently determined the values of σ(Z 3, m, m) for m ≥ 4. In this paper, we completely determine the values of σ(Z 3, m, n) for m ≥ n ≥ 4.

A set $S\subseteq V(G)$ is a liar's dominating set ($lds$) of graph $G$ if $|N_G[v]\cap S|\geq 2$ for every $v\in V(G)$ and $|(N_G[u]\cup N_G[v])\cap S|\geq 3$ for any two distinct vertices $u,v \in V(G)$. The liar's domination number of $G$, denoted by $\gamma_{LR}(G)$, is the smallest cardinality of a liar's dominating set of $G$. In this paper we study the concept of liar's domination in the join, corona, and lexicographic product of graphs.

Let R be a commutative semiring with nonzero identity and H be a multiplicative-prime subset of R. The generalized total graph of a commutative semiring R is the (undirected) graph \(GT_{H}(R)\) whose vertices are all elements of R and two distinct vertices x and y are adjacent if and only if \(x+y\in H\). In this paper, we investigate the structure of \(GT_{H}(R)\) and we also study the two (induced) subgraphs \(GT_{H}(H)\) and \(GT_{H}(R{\setminus } H)\) with vertex-sets H and \(R{\setminus } H\).

In this paper we prove the containment I ( n m ) ⊂ M ( n − 1 ) m I m I^{(nm)}\subset M^{(n-1)m}I^m , for a radical ideal I I of s s general points in P n \mathbb {P}^n , where s ≥ 2 n s\geq 2^n . As a corollary we get that the Chudnovsky Conjecture holds for a very general set of at least 2 n 2^n points in P n \mathbb {P}^n .

A proper edge-k-coloring of a graph G is a mapping from E(G) to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different fromthe sumof colors taken on the edges incident to v. Let χ′Σ(G) denote the smallest value k in such a coloring of G. This parameter makes sense for graphs containing no isolated edges (we call such graphs normal). The maximum average degree mad(G) of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad(G) < 5/2, then χ′Σ(G) ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials $\mathcal C$ and show that if $p\in \cal C$ and there is a disk $D$ centered at zero in the complex plane such that $p(G)$ does not vanish on $D$ for all bounded degree graphs $G$, then for each $z$ in the interior of $D$ there exists a deterministic polynomial-time approximation algorithm for evaluating $p(G)$ at $z$. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated by. Barvinok, which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems., 27 pages; some changes have been made based on referee comments. In particular a tiny error in Proposition 4.4 has been fixed. The introduction and concluding remarks have also been rewritten to incorporate the most recent developments. Accepted for publication in SIAM Journal on Computation

Let m, r, k be three positive integers. Let G be a graph with vertex set V(G) and edge set E(G), and let f: V(G) → N be a function such that f ( x ) ≥ ( k + 2 ) r − 1 for any x ∈ V(G). Let H1, H2, … , Hk be k vertex disjoint mr-subgraphs of a graph G. In this paper, we prove that every ( 0 , m f − ( m − 1 ) r ) -graph admits a (0, f)-factorization randomly r-orthogonal to each Hi ( i = 1 , 2 , … , k ).

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay+(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay+(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z3 and Zn2n, n ≥ 1, where Zk is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.

Let G be a finite group and NA(G) denote the number of conjugacy classes of all nonabelian subgroups of non-prime-power order of G. The Symbol π(G) denote the set of the prime divisors of |G|. In this paper we establish lower bounds on NA(G). In fact, we show that if G is a finite solvable group, then NA(G) = 0 or NA(G) ≥ 2|π(G)|−2, and if G is non-solvable, then NA(G) ≥ |π(G)| + 1. Both lower bounds are best possible.

In the paper, the authors present some properties, including convexity, complete monotonicity, product inequalities, and determinantal inequalities, of the large Schroder numbers and find three relations between the Schroder numbers and central Delannoy numbers. Moreover, the authors sketch generalizing the Schroder numbers and central Delannoy numbers and their generating functions.

Assume G is a finite group and H a subgroup of G. If there exists a subgroup K of G such that G = HK and H ∩ K = 1, then K is said to be a complement to H in G. A finite p-group G is called an NC-group if all its proper normal subgroups not contained in Φ(G) have complements. In this paper, some properties of NC-groups are investigated and some classes of NC-groups are classified.

Let R be a commutative ring with identity and let Z(R, k) be the set of all k-zero-divisors in R and $$k>2$$ an integer. The k-zero-divisor hypergraph of R, denoted by $$\mathcal {H}_k(R)$$ , is a hypergraph with vertex set Z(R, k), and for distinct elements $$x_1,x_2,\ldots ,x_k$$ in Z(R, k), the set $$\{x_1,x_2, \ldots , x_k\}$$ is an edge of $$\mathcal {H}_k(R)$$ if and only if $$\prod \limits _{i=1}^kx_i =0$$ and the product of any $$(k-1)$$ elements of $$\{x_1,x_2,\ldots ,x_k\}$$ is nonzero. In this paper, we characterize all finite commutative non-local rings R with identity whose $$\mathcal {H}_3(R)$$ has crosscap one.

In this paper, we investigate the intersection numbers of nearly Kirkman triple systems. JN[v] is the set of all integers k such that there is a pair of NKTS(v)s with a common uncovered collection of 2-subset intersecting in k triples. It has been established that \({J_N}\left[ v \right] = \left\{ {0,1,...,\frac{{v\left( {v - 2} \right)}}{6} - 6,\frac{{v\left( {v - 2} \right)}}{6} - 4,\frac{{v\left( {v - 2} \right)}}{6}} \right\}\) for any integers v = 0 (mod 6) and v ≥ 66. For v ≤ 60, there are 8 cases left undecided.

Let R be a commutative ring with nonzero identity. We denote by AG(R) the annihilator graph of R, whose vertex set consists of the set of nonzero zero-divisors of R, and two distint vertices x and y are adjacent if and only if \(\mathrm {ann}(x) \cup \mathrm {ann}(y) \ne \mathrm {ann}(xy)\), where for \(t\in R\), we set \(ann(t) := \lbrace r\in R\ \vert \ rt=0\rbrace \). In this paper, we define the annihiator-ideal graph of R, which is denoted by \(A_{I}(R)\), as an undirected graph with vertex set \(A^*(R)\), and two distinct vertices I and J are adjacent if and only if \(\mathrm {ann}(I) \cup \mathrm {ann}(J) \ne \mathrm {ann}(IJ)\). We study some basic properties of \(A_{I}(R)\) such as connectivity, diameter and girth. Also we investigate the situations under which the graphs AG(R) and \(A_{I}(R)\) are coincide. Moreover, we examin the planarity of the graph \(A_{I}(R)\).

Let X denote a compact metric space with distance d and F : X × ℝ → X or Ft : X → X denote a C0-flow. From the point of view of ergodic theory, all important dynamical behaviors take place on a full measure set. The aim of this paper is to introduce the notion of Banach upper density recurrent points and to show that the closure of the set of all Banach upper density recurrent points equals the measure center or the minimal center of attraction for a C0-flow. Moreover, we give an example to show that the set of quasi-weakly almost periodic points can be included properly in the set of Banach upper density recurrent points, and point out that the set of Banach upper density recurrent points can be included properly in the set of recurrent points.

In this paper, we analyze the tree reconstruction problem, which is to determine whether symbols at the nth level of the tree provide information on the root as n→∞.This problem has wide applications in various fields such as biology, information theory, and statistical physics, and its close connections to the clustering problem in the setting of the stochastic block model (SBM) have been well established. Inspired by the recently proposed q1+q2 SBM, we extend the classical works on the Ising model (Borgs et al. [2006]) and the Potts model (Sly [2011]), by studying a general model which incorporates the characteristics of both Ising and Potts through different in-community and out-community transition probabilities, and rigorously establishing the exact conditions for reconstruction.