Search

We correct a mistake in a lemma in the paper cited in the title and show that it did not affect any of the other results of the paper. To this end, we prove results on linearly disjoint field extensions that do not seem to be commonly known. We give an example to show that a separability assumption in one of these results cannot be dropped (doing so had led to the mistake). Further, we discuss recent generalizations of the original classification of defect extensions.

This article is intended to indicate and discuss some errors in N. Lavi’s paper “A Ganzstellensatz for semi-algebraic sets and a boundedness criterion for rational functions”.

The spectral gap conjecture of M. van den Berg [2, formula (65)] asserts that λ2 − λ1 ≥ 3π for all convex euclidean domains of diameter 1, where λ1 and λ2 denote the first two eigenvalues of the Dirichlet Laplacian. Notice that equality holds for the 1-dimensional unit interval, which can be regarded also as a degenerate n-dimensional rectangular box. The gap estimate is conjectured to hold more generally for Schrodinger operators with convex potentials, under Dirichlet boundary conditions; see the work of S.-T. Yau and collaborators [9, 11]. This Schrodinger gap conjecture was proved some time ago in 1 dimension by R. Lavine [8], and more recently in all dimensions by B. Andrews and J. Clutterbuck [1]. The proof in this journal by H. Donnelly [3] of the original gap conjecture in 2 dimensions (for the Dirichlet Laplacian with zero potential) is not correct. The Editors of Mathematische Zeitschrift have asked us to describe the flaws in the proof, in order to clarify the state of the literature. Donnelly’s approach to the problem is a natural one: first perform a shape optimization to rule out a non-degenerate minimizing domain, and then analyze the spectral gap for a sequence of domains degenerating to an interval, with the help of results by D. Jerison [5]. (For some history on this approach, and on the gap conjecture more generally, see the report on the AIM meeting “Low Eigenvalues of Laplace and Schrodinger Operators” [10], especially page 12 of the open problems list.) The error lies in the proof of the shape optimization step, as we now explain. Donnelly wishes to prove that no minimizing domain can exist for

In this note, we improve some results of Granville and Soundararajan on the distribution of values of the truncated random Euler product L ( 1 , X ; y ) : = ∏ p ⩽ y ( 1 − X ( p ) / p ) −1 , where the X ( p ) are independent random variables, taking the values ±1 with equal probability p / 2 ( p + 1 ) and 0 with probability 1 / ( p + 1 ) .

In this paper we study bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when access to shared randomness is free. For synchronous correlations, we show a correspondence between the minimal entanglement dimension and the completely positive semidefinite rank of an associated matrix. We then study optimization over the set of synchronous correlations by investigating quantum graph parameters. We unify existing bounds on the quantum chromatic number and the quantum stability number by placing them in the framework of tracial optimization. In particular, we show that the projective packing number, the projective rank, and the tracial rank arise naturally when considering tracial analogues of the Lasserre hierarchy for the stability and chromatic number of a graph. We also introduce semidefinite programming hierarchies converging to the commuting quantum chromatic number and commuting quantum stability number., Comment: 26 pages

The unit-cell reduction described by Selling and used by Delone (Delaunay) is explained in a simple form., The unit-cell reduction described by Selling and used by Delone (whose early publications were under the spelling Delaunay) is explained in a simple form. The transformations needed to implement the reduction are listed. The simplicity of this reduction contrasts with the complexity of Niggli reduction.

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to turn $\delta$ into a plane drawing of $G$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate, and we give explicit bounds on shift$(G,\delta)$ when $G$ is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem., Comment: This paper has been merged with http://arxiv.org/abs/0709.0170

International audience; In this paper, we present an algebraic attack against the Flurry and Curry block ciphers [12,13]. Usually, algebraic attacks against block ciphers only require one message/ciphertext pair to be mounted. In this paper, we investigate a different approach. Roughly, the idea is to generate an algebraic system from the knowledge of several well chosen correlated message/ciphertext pairs. Flurry and Curry are two families of ciphers which fully parametrizable and having a sound design strategy against the most common statistical attacks; i.e. linear and differential attacks. These ciphers are then targets of choices for algebraic attacks. It turns out that our new approach permits to go one step further in the (algebraic) cryptanalysis of difficult instances of Flurry and Curry. To explain the behavior of our attack, we have established an interesting connection between algebraic attacks and high order differential cryptanalysis [32]. From extensive experiments, we estimate that our approach – that we will call ”algebraic-high order differential” cryptanalysis – is polynomial when the Sbox is a power function. As a proof of concept, we have been able to break Flurry/Curry – up to 8 rounds – in few hours. We have also investigated the more difficult (and interesting case) of the inverse function. For such function, we have not been able to bound precisely the theoretical complexity, but our experiments indicate that our approach permits to obtain a significant practical gain. We have attacked Flurry/Curry using the inverse Sbox up to 8 rounds.

The mathematical analysis of the shape of chemical reactors is studied in this paper through the research of the optimization of its effectiveness η such as introduced by R. Aris around 1960. Although our main motivation is the consideration of reactors specially designed for the treatment of wastewaters our results are relevant also in more general frameworks. We simplify the modeling by assuming a single chemical reaction with a monotone kinetics leading to a parabolic equation with a non-necessarily differentiable function. In fact we consider here the case of a single, non-reversible catalysis reaction of chemical order q,00). We assume the chemical reactor of cylindrical shape Ω=G×(0,H) with G and open regular set of R2 not necessarily symmetric. We show that among all the sections G with prescribed area the ball is the set of lowest effectiveness η(t,G). The proof uses the notions of Steiner rearrangement. Finally, we show that if the height H is small enough then the effectiveness can be made as close to 1 as desired. 888 The mathematical analysis of the shape of chemical reactors is studied in this paper through the research of the optimization of its effectiveness (Formula presented.) such as introduced by R. Aris around 1960. Although our main motivation is the consideration of reactors specially designed for the treatment of wastewaters our results are relevant also in more general frameworks. We simplify the modeling by assuming a single chemical reaction with a monotone kinetics leading to a parabolic equation with a non-necessarily differentiable function. In fact we consider here the case of a single, non-reversible catalysis reaction of chemical order (Formula presented.) (i.e., the kinetics is given by (Formula presented.) for some (Formula presented.)). We assume the chemical reactor of cylindrical shape (Formula presented.) with G and open regular set of (Formula presented.) not necessarily symmetric. We show that among all the sections G with prescribed area the ball is the set of lowest effectiveness (Formula presented.). The proof uses the notions of Steiner rearrangement. Finally, we show that if the height H is small enough then the effectiveness can be made as close to 1 as desired.

In a recent paper, the first author provided some lower bounds to solutions of the equations of Fermat and Catalan, based on local power series developments at the ramified prime of a prime cyclotomic extension. Although both equations have in fact been proved not to have any unknown solutions, these improved bounds are interesting in the context of a new effective abc inequality announced in the paper \cite{MFHMP} based on Mochizuki's \cite{Mo}[IUT-IV, Theorem A]. In this paper we provide a strengthening of the lower bound for FLT2, which is necessary in order to take advantage of the best upper bounds for primes $p$ for which it was verified on a computer that FLT2 has no solutions., Submitted, under review

The present paper introduces new classes of Stancu–Kantorovich operators constructed in the King sense. For these classes of operators, we establish some convergence results, error estimations theorems and graphical properties of approximation for the classes considered, namely, operators that preserve the test functions e0(x)=1 and e1(x)=x, e0(x)=1 and e2(x)=x2, as well as e1(x)=x and e2(x)=x2. The class of operators that preserve the test functions e1(x)=x and e2(x)=x2 is a genuine generalization of the class introduced by Indrea et al. in their paper “A New Class of Kantorovich-Type Operators”, published in Constr. Math. Anal.

The so called Landis conjecture states that if a solution of the equation $$\Delta u+V(x)u=0$$ in an exterior domain decays faster than $e^{-\kappa|x|}$, for some $\kappa>\sqrt{\sup |V|}$, then it must be identically equal to $0$. This property can be viewed as a unique continuation at infinity (UCI) for solutions satisfying a suitable exponential decay. The Landis conjecture was disproved by Meshkov in the case of complex-valued functions, but it remained open in the real case. In the 2000s, several papers have addressed the issue of the UCI for linear elliptic operators with real coefficients. The results that have been obtained require some kind of sign condition, either on the solution or on the zero order coefficient of the equation. The Landis conjecture is still open nowadays in its general form. In the present paper, we start with considering a general (real) elliptic operator in dimension $1$. We derive the UCI property with a rate of decay $\kappa$ which is sharp when the coefficients of the operator are constant. In particular, we prove the Landis conjecture in dimension $1$, and we can actually reach the threshold value $\kappa=\sqrt{\sup |V|}$. Next, we derive the UCI property -- and then the Landis conjecture -- for radial operators in arbitrary dimension. Finally, with a different approach, we prove the same result for positive supersolutions of general elliptic equations.

In this paper, we will prove some fundamental properties of the discrete power mean operator M p u n = 1 / n ∑ k = 1 n u p k 1 / p , for n ∈ I ⊆ ℤ + , of order p , where u is a nonnegative discrete weight defined on I ⊆ ℤ + the set of the nonnegative integers. We also establish some lower and upper bounds of the composition of different operators with different powers. Next, we will study the structure of the generalized discrete class B p q B of weights that satisfy the reverse Hölder inequality M q u ≤ B M p u , for positive real numbers p , q , and B such that 0 < p < q and B > 1 . For applications, we will prove some self-improving properties of weights from B p q B and derive the self improving properties of the discrete Gehring weights as a special case. The paper ends by a conjecture with an illustrative sharp example.

During the last few decades, domination theory has been one of the most active areas of research within graph theory. Currently, there are more than 4400 published papers on domination and related parameters. In the case of total domination, there are over 580 published papers, and 50 of them concern the case of product graphs. However, none of these papers discusses the case of rooted product graphs. Precisely, the present paper covers this gap in the theory. Our goal is to provide closed formulas for the total domination number of rooted product graphs. In particular, we show that there are four possible expressions for the total domination number of a rooted product graph, and we characterize the graphs reaching these expressions.

In 2006, A. Stakhov introduced a new coding/decoding process based on generating matrices of the Fibonacci p-numbers, which he called the Fibonacci coding/decoding method. Stakhov&rsquo, s papers have motivated many other scientists to seek certain generalizations by introducing new additional coefficients into recurrence of Fibonacci p-numbers. In 2013, I. Włoch et al. studied (2,q)-distance Fibonacci numbers F2(q,n) and found some of their combinatorial properties. In this paper, we state a new coding theory based on the sequence (Tq(n))n=&minus, &infin, which is an extension of Włoch&rsquo, s sequence (F2(q,n))n=0&infin

The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of Constraint Satisfaction problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as Travelling Salesman or Steiner Tree. We demonstrate the technique for Travelling Salesman and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander’s parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current best approximation hardness value for TSP from $$\frac{123}{122}$$ 123 122 (Karpinski et al. in J Comput Syst Sci 81(8):1665–1677, 2015) to $$\frac{117}{116}$$ 117 116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems.

In this paper, we study some optimal inequalities of the Riccati type and of the Bihari type. We also consider nonoptimal inequalities of the Wendorf type. At the same time, we get a partial answer to Problems 5 and 9, formulated by I. A. Rus. This paper is also motivated by the fact that, in many inequalities, the upper bound is not an optimal one.

Let Ckn,l be a simple closed k-curves with l elements in Zn and W:=Ckn,l&or, ⋯&or, Ckn,l︷m-times be an m-iterated digital wedges of Ckn,l, and F(Conk(W)) be an alignment of fixed point sets of W. Then, the aim of the paper is devoted to investigating various properties of F(Conk(W)). Furthermore, when proceeding with this work, this paper addresses several unsolved problems. To be specific, we firstly formulate an alignment of fixed point sets of Ckn,l, denoted by F(Conk(Ckn,l)), where l(&ge, 7) is an odd natural number and k&ne, 2n. Secondly, given a digital image (X,k) with X♯=n, we find a certain condition that supports n&minus, 1,n&minus, 2&isin, F(Conk(X)). Thirdly, after finding some features of F(Conk(W)), we develop a method of making F(Conk(W)) perfect according to the (even or odd) number l of Ckn,l. Finally, we prove that the perfectness of F(Conk(W)) is equivalent to that of F(Conk(Ckn,l)). This can play an important role in studying fixed point theory and digital curve theory. This paper only deals with k-connected digital images (X,k) such that X♯&ge, 2.

Let $\mathbb{R}$ be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in $\mathbb{R}^n$ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity $(nd)^{O(n\log(n))}$ for computing the real isolated points of real algebraic hypersurfaces of degree $d$. It allows us to solve in practice instances which are out of reach of the state-of-the-art., Conference paper ISSAC 2020

In this paper, we introduce a method known aspolynomial frame approximationfor approximating smooth, multivariate functions defined on irregular domains in$d$dimensions, where$d$can be arbitrary. This method is simple, and relies only on orthogonal polynomials on a bounding tensor-product domain. In particular, the domain of the function need not be known in advance. When restricted to a subdomain, an orthonormal basis is no longer a basis, but a frame. Numerical computations with frames present potential difficulties, due to the near-linear dependence of the truncated approximation system. Nevertheless, well-conditioned approximations can be obtained via regularization, for instance, truncated singular value decompositions. We comprehensively analyze such approximations in this paper, providing error estimates for functions with both classical and mixed Sobolev regularity, with the latter being particularly suitable for higher-dimensional problems. We also analyze the sample complexity of the approximation for sample points chosen randomly according to a probability measure, providing estimates in terms of the correspondingNikolskii inequalityfor the domain. In particular, we show that the sample complexity for points drawn from the uniform measure is quadratic (up to a log factor) in the dimension of the polynomial space, independently of $d$, for a large class of nontrivial domains. This extends a well-known result for polynomial approximation in hypercubes.

We study measures $\mu$ on the plane with two independent Alberti representations. It is known, due to Alberti, Cs\"ornyei, and Preiss, that such measures are absolutely continuous with respect to Lebesgue measure. The purpose of this paper is to quantify the result of A-C-P. Assuming that the representations of $\mu$ are bounded from above, in a natural way to be defined in the introduction, we prove that $\mu \in L^{2}$. If the representations are also bounded from below, we show that $\mu$ satisfies a reverse H\"older inequality with exponent $2$, and is consequently in $L^{2 + \epsilon}$ by Gehring's lemma. A substantial part of the paper is also devoted to showing that both results stated above are optimal., Comment: 16 pages, 4 figures. v2: corrected typos, expanded introduction

In many scientific disciplines, finding hidden influential factors behind observational data is essential but challenging. The majority of existing approaches, such as the independent component analysis (${\mathrm{ICA}}$), rely on linear transformation, that is, true signals are linear combinations of hidden components. Motivated from analyzing nonlinear temporal signals in neuroscience, genetics, and finance, this paper proposes the “maximum independent component analysis” (${\mathrm{MaxICA}}$), based on max-linear combinations of components. In contrast to existing methods, ${\mathrm{MaxICA}}$ benefits from focusing on significant major components while filtering out ignorable components. A major tool for parameter learning of ${\mathrm{MaxICA}}$ is an augmented genetic algorithm, consisting of three schemes for the elite weighted sum selection, randomly combined crossover, and dynamic mutation. Extensive empirical evaluations demonstrate the effectiveness of ${\mathrm{MaxICA}}$ in either extracting max-linearly combined essential sources in many applications or supplying a better approximation for nonlinearly combined source signals, such as $\mathrm{EEG}$ recordings analyzed in this paper.

Different authors have shown strong relationships between ordinal pattern based entropies and the Kolmogorov&ndash, Sinai entropy, including equality of the latter one and the permutation entropy, the whole picture is however far from being complete. This paper is updating the picture by summarizing some results and discussing some mainly combinatorial aspects behind the dependence of Kolmogorov&ndash, Sinai entropy from ordinal pattern distributions on a theoretical level. The paper is more than a review paper. A new statement concerning the conditional permutation entropy will be given as well as a new proof for the fact that the permutation entropy is an upper bound for the Kolmogorov&ndash, Sinai entropy. As a main result, general conditions for the permutation entropy being a lower bound for the Kolmogorov&ndash, Sinai entropy will be stated. Additionally, a previously introduced method to analyze the relationship between permutation and Kolmogorov&ndash, Sinai entropies as well as its limitations will be investigated.

Both the Thue-Morse and Rudin-Shapiro sequences are not suitable sequences for cryptography since their expansion complexity is small and their correlation measure of order 2 is large. These facts imply that these sequences are highly predictable despite the fact that they have a large maximum order complexity. Sun and Winterhof (2019) showed that the Thue-Morse sequence along squares keeps a large maximum order complexity. Since, by Christol's theorem, the expansion complexity of this rarefied sequence is no longer bounded, this provides a potentially better candidate for cryptographic applications. Similar results are known for the Rudin-Shapiro sequence and more general pattern sequences. In this paper we generalize these results to any polynomial subsequence (instead of squares) and thereby answer an open problem of Sun and Winterhof. We conclude this paper by some open problems., Comment: 11 pages

In a recent paper, for univariate max-product sampling operators based on general kernels with bounded generalized absolute moments, we have obtained several \begin{document}$ L^{p}_{\mu} $\end{document} convergence properties on bounded intervals or on the whole real axis. In this paper, firstly we obtain quantitative estimates with respect to a \begin{document}$ K $\end{document} -functional, for the multivariate Kantorovich variant of these max-product sampling operators with the integrals written in terms of Borel probability measures. Applications of these approximation results to learning theory are obtained.

Statistical analysis of network is an active research area and the literature counts a lot of papers concerned with network models and statistical analysis of networks. However, very few papers deal with missing data in network analysis and we reckon that, in practice, networks are often observed with missing values. In this paper we focus on the Stochastic Block Model with valued edges and consider a MCAR setting by assuming that every dyad (pair of nodes) is sampled identically and independently of the others with probability $\rho > 0$. We prove that maximum likelihood estimators and its variational approximations are consistent and asymptotically normal in the presence of missing data as soon as the sampling probability $\rho$ satisfies $\rho\gg\log(n)/n$., Comment: 32 pages, 0 figures. arXiv admin note: text overlap with arXiv:1704.06629

The main purpose of this paper is to consider the strong law of large numbers for random sets in fuzzy metric space. Since many years ago, limited theorems have been expressed and proved for fuzzy random variables, but despite the uncertainty in fuzzy discussions, the nonfuzzy metric space has been used. Given that the fuzzy random variable is defined on the basis of random sets, in this paper, we generalize the strong law of large numbers for random sets in the fuzzy metric space. The embedded theorem for compact convex sets in the fuzzy normed space is the most important tool to prove this generalization. Also, as a result and by application, we use the strong law of large numbers for random sets in the fuzzy metric space for the bootstrap mean.

A cut $\varepsilon$-sparsifier of a weighted graph $G$ is a re-weighted subgraph of $G$ of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $\varepsilon$. Since their introduction by Bencz\'ur and Karger [STOC'96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA'17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains., Comment: Full version of a STACS'19 paper

This paper aims to study vector optimization through improvement sets in locally convex spaces. This investigation could be viewed as an extension of the work of Lalitha and Chatterjee (J Optim Theory Appl 166: 825–843, 2015) who studied an open problem on stability posed by Chicco et al., in normed linear spaces. This paper also establishes some existence results for this kind of vector optimization using the celebrated KKM theorem (or Fan’s Lemma, which is more common in the literature). Some examples illustrating the advantage of this work than that of Lalitha and Chatterjee (2015) are included too.

In the recent paper [Jin, Kolda & Ward, arXiv:1909.04801], it is proved that the Kronecker fast Johnson-Lindenstrauss transform (KFJLT) is, in fact, a Johnson-Lindenstrauss transform, which had previously only been conjectured. In this paper, we provide an alternative proof of this, for when the KFJLT is applied to Kronecker vectors, using a coherence and sampling argument. Our proof yields a different bound on the embedding dimension, which can be combined with the bound in the paper by Jin et al. to get a better bound overall. As a stepping stone to proving our result, we also show that the KFJLT is a subspace embedding for matrices with columns that have Kronecker product structure. Lastly, we compare the KFJLT to four other sketch techniques in numerical experiments on both synthetic and real-world data., Accepted to Linear Algebra and its Applications

Let k ≤ n be two positive integers and q a prime power. The basic question in minimal linear codes is to determine if there exists an [ n , k ] q minimal linear code. The first objective of this paper is to present a new sufficient and necessary condition for linear codes to be minimal. Using this condition, it is easy to construct minimal linear codes or to prove some linear codes are minimal. The second objective of this paper is to use the new sufficient and necessary condition to partially give an answer to the basic question in minimal linear codes. The third objective of this paper is to present four classes of minimal linear codes, which generalize the results about the binary case given in X. Li and Q. Yue (2020) [13] . One can find that our method is much easier and more effective.

The multiplicative coalescent is a mean-field Markov process in which any pair of blocks coalesces at rate proportional to the product of their masses. In Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3) each extreme eternal version of the multiplicative coalescent was described in three different ways, one of which matched its (marginal) law to that of the ordered excursion lengths above past minima of a certain Lévy-type process. ¶ Using a modification of the breadth-first-walk construction from Aldous (Ann. Probab. 25 (1997) 812–854) and Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3), and some new insight from the thesis by Uribe Bravo (Markovian bridges, Brownian excursions, and stochastic fragmentation and coalescence (2007) UNAM), this work settles an open problem (3) from Aldous (Ann. Probab. 25 (1997) 812–854) in the more general context of Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3). Informally speaking, each eternal version is entirely encoded by its Lévy-type process, and contrary to Aldous’ original intuition, the time for the multiplicative coalescent does correspond to the linear increase in the constant part of the drift of the Lévy-type process. In the “standard multiplicative coalescent” context of Aldous (Ann. Probab. 25 (1997) 812–854), this result was first announced by Armendáriz in 2001, while its first published proof is due to Broutin and Marckert (Probab. Theory Related Fields 166 (2016) 515–552), who simultaneously account for the process of excess (or surplus) edge counts.

In this paper, we establish coincidence point and common fixed point theorems involving two pairs of weakly compatible mapping satisfying contraction condition with complex coefficient are proved in complex valued metric space. The presented theorems generalize, extend and improve many existing results in the literature. An example is given at the end of the paper.

In this paper, we first prove an integral majorization theorem related to integral inequalities for functions defined on rectangles. We then apply the result to establish some new integral inequalities for functions defined on rectangles. The results obtained are generalizations of weighted Favard’s inequality, which also provide a generalization of the results given by Maligranda et al. (J. Math. Anal. Appl. 190:248–262, 1995) in an earlier paper.

One major open conjecture in the area of critical random graphs, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade [23, 24, 28, 63] is as follows: for a wide array of random graph models with degree exponent $\tau\in (3,4)$, distances between typical points both within maximal components in the critical regime as well as on the minimal spanning tree on the giant component in the supercritical regime scale like $n^{(\tau-3)/(\tau-1)}$. In this paper we study the metric space structure of maximal components of the multiplicative coalescent, in the regime where the sizes converge to excursions of L\'evy processes "without replacement" [10], yielding a completely new class of limiting random metric spaces. A by-product of the analysis yields the continuum scaling limit of one fundamental class of random graph models with degree exponent $\tau\in (3,4)$ where edges are rescaled by $n^{-(\tau-3)/(\tau-1)}$ yielding the first rigorous proof of the above conjecture. The limits in this case are compact "tree-like" random fractals with finite fractal dimensions and with a dense collection of hubs (infinite degree vertices) a finite number of which are identified with leaves to form shortcuts. In a special case, we show that the Minkowski dimension of the limiting spaces equal $(\tau-2)/(\tau-3)$ a.s., in stark contrast to the Erd\H{o}s-R\'{e}nyi scaling limit whose Minkowski dimension is 2 a.s. It is generally believed that dynamic versions of a number of fundamental random graph models, as one moves from the barely subcritical to the critical regime can be approximated by the multiplicative coalescent. In work in progress, the general theory developed in this paper is used to prove analogous limit results for other random graph models with degree exponent $\tau\in (3,4)$., Comment: 71 pages, 5 figures, To appear in Probability Theory and Related Fields

In this paper, some properties of the interior of positive dual cones are discussed. With the help of dilating cones, a new notion of inner superefficient points for a set is introduced. Under the assumption of near cone-subconvexlikeness, by applying the separation theorem for convex sets, the relationship between inner superefficient points and superefficient points is established. Compared to other approximate points in the literature, inner superefficient points in this paper are really ‘approximate’.

The present paper deals with nonoscillation problem for the Sturm–Liouville half-linear differential equation $$\begin{aligned} \big (r(t)\phi _p(x')\big )' + c(t)\phi _p(x) = 0, \end{aligned}$$ where r, $$c\!:[a,\infty ) \rightarrow \mathbb {R}$$ are continuous functions, $$r(t) > 0$$ for $$t \ge a$$ , and $$\phi _p(z) = |z|^{p-2}z$$ with $$p > 1$$ . The purpose of this paper is to show that it is possible to broaden the application range of Hille-Wintner type nonoscillation criteria. To this end, we derive a comparison theorem by means of Riccati’s technique. Our result is new even in the linear case that $$p = 2$$ . By the obtained result, we can compare two differential equations having a different power p of the above-mentioned type. To illustrate our comparison theorem, we present two examples of which all non-trivial solutions of the Sturm-Liouville linear differential equation are nonoscillatory even if $$\int _a^t\!\frac{1}{r(s)}ds\int _t^\infty \!\!c(s)ds$$ or $$\int _t^\infty \!\!\frac{1}{r(s)}ds\int _a^t\!c(s)ds$$ is less than the lower bound $$-3/4$$ .

In this paper, we investigate the existence and multiplicity of nontrivial weak solutions for a class of nonlinear impulsive ( q , p ) $(q,p)$ -Laplacian dynamical systems. The key contributions of this paper lie in (i) Exploiting the least action principle, we deduce that the system we are interested in has at least one weak solution if the potential function has sub- ( q , p ) $(q,p)$ growth or ( q , p ) $(q,p)$ growth; (ii) Employing a critical point theorem due to Ding (Nonlinear Anal. 25(11):1095-1113, 1995), we derive that the system involved has infinitely many weak solutions provided that the potential function is even.

We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It is known that, for the Lebesgue measure $d\mu(x) = dx$, one may show an error bound $O(1/\sqrt{r})$ if $h$ is a sum-of-squares density, and an $O(1/r)$ error bound if $h$ is the density of a beta distribution. In this paper, we show an error bound of $O(1/r^2)$, if $d\mu(x) = \left(\prod_{i=1}^n \sqrt{1-x_i^2} \right)^{-1}dx$ (the well-known measure in the study of orthogonal polynomials), and $h$ has a Schm\"udgen-type representation with respect to $[-1,1]^n$, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels, and in particular on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities., Comment: 21 pages, 3 figures, published in SIAM Journal on Optimization, 27(1):347-367, March 2017. This arXiv version is an updated version of the journal paper. Typos were corrected in the proofs of Lemmata 2.2 and 3.5 and Theorem 4.2

This paper explores a new language of neighbourhood structures where existential information can be given about what kind of worlds occur in a neighbourhood of a current world. The resulting system of ‘instantial neighbourhood logic’ INL has a nontrivial mix of features from relational semantics and from neighbourhood semantics. We explore some basic model-theoretic behavior, including a matching notion of bisimulation, and give a complete axiom system for which we prove completeness by a new normal form technique. In addition, we relate INL to other modal logics by means of translations, and determine its precise SAT complexity. Finally, we discuss proof-theoretic fine-structure of INL in terms of semantic tableaux and some expressive fine-structure in terms of fragments, while discussing concrete illustrations of the instantial neighborhood language in topological spaces, in games with powers for players construed in a new way, as well as in dynamic logics of acquiring or deleting evidence. We conclude with some coalgebraic perspectives on what is achieved in this paper. Many of these final themes suggest follow-up work of independent interest.

In the paper we consider a nonlinear control system governed by the Volterra integral operator. Using a version of the global implicit function theorem we prove that the control system under consideration is well-posed and robust, i.e. for any admissible control \(u\) there exists a uniquely defined trajectory \(x_{u}\) which continuously depends on control \(u\) and the operator \(u\mapsto x_{u}\) is continuously differentiable. The novelty of this paper is, among others, the application of the Bielecki norm in the space of solutions which allows us to weaken standard assumptions.

After the inception of the concept of a fuzzy metric by I. Kramosil and J. Michalek, and especially after its revision by A. George and G. Veeramani, the attention of many researches was attracted to the topology induced by a fuzzy metric. In most of the works devoted to this subject the resulting topology is an ordinary, that is a crisp one. Recently some researchers showed interest in the fuzzy-type topologies induced by fuzzy metrics. In particular, in the paper (J.J. Mi\~{n}ana, A. \v{S}ostak, {\it Fuzzifying topology induced by a strong fuzzy metric}, Fuzzy Sets and Systems, 6938 DOI information: 10.1016/j.fss.2015.11.005.) a fuzzifying topology ${\mathcal T}:2^X \to [0,1]$ induced by a fuzzy metric $m: X\times X \times [0,\infty)$ was constructed. In this paper we extend this construction to get the fuzzy topology ${\mathcal T}: [0,1]^X \to [0,1]$ and study some properties of this fuzzy topology.54A

Let be a polynomial of degree D. Computing the set of generalized critical valuesof the mapping (i.e. ) is an important step in algorithms computing sampling points in semi-algebraic sets defined by a single inequality. A previous algorithm allows us to compute the set of generalized critical values of $\widetilde{f}$. This one is based on the computation of the critical locus of a projection on a plane P. This plane Pmust be chosen such that some global properness properties of some projections are satisfied. These properties, which are generically satisfied, are difficult to check in practice. Moreover, choosing randomly the plane Pinduces a growth of the coefficients appearing in the computations. We provide here a new certified algorithm computing the set of generalized critical values of $\widetilde{f}$. This one is still based on the computation of the critical locus on a plane P. The certification process consists here in checking that this critical locus has dimension 1 (which is easy to check in practice), without any assumption of global properness. Moreover, this allows us to limit the growth of coefficients appearing in the computations by choosing a plane Pdefined by sparse equations. Additionally, we prove that the degree of this critical curve is bounded by $(D-1)^{n-1}-\mathfrak{d}$ where $\mathfrak{d}$ is the sum of the degrees of the positive dimensional components of the ideal $\langle \frac{\partial f}{\partial X_1}, \ldots,\frac{\partial f}{\partial X_n}\rangle$. We also provide complexity estimates on the number of arithmetic operations performed by a probabilistic version of our algorithm. Practical experiments at the end of the paper show the relevance and the importance of these results which improve significantly in practice previous contributions.

The main objective of this paper is the following two results. (1) There exists a computable bi-orderable group that does not have a computable bi-ordering; (2) There exists a bi-orderable, two-generated recursively presented solvable group with undecidable word problem. Both of the groups can be found among two-generated solvable groups of derived length $3$. (1) answers a question posed by Downey and Kurtz; (2) answers a question posed by Bludov and Glass in Kourovka Notebook. One of the technical tools used to obtain the main results is a computational extension of an embedding theorem of B. Neumann that was studied by the author earlier. In this paper we also compliment that result and derive new corollaries that might be of independent interest., Added Subsection 1.1 which is a revised version of Section 2 from v1. Other noticeable revisions, especially, in Section 4

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

Minimal linear codes are algebraic objects which gained interest in the last twenty years, due to their link with Massey's secret sharing schemes. In this context, Ashikhmin and Barg provided a useful and a quite easy to handle sufficient condition for a linear code to be minimal, which has been applied in the construction of many minimal linear codes. In this paper, we generalize some recent constructions of minimal linear codes which are not based on Ashikhmin-Barg's condition. More combinatorial and geometric methods are involved in our proofs. In particular, we present a family of codes arising from particular blocking sets, which are well-studied combinatorial objects. In this context, we will need to define cutting blocking sets and to prove some of their relations with other notions in blocking sets' theory. At the end of the paper, we provide one explicit family of cutting blocking sets and related minimal linear codes, showing that infinitely many of its members do not satisfy the Ashikhmin-Barg's condition., 13 pages

As is well-known, the benefit of restricting L&eacute, vy processes without positive jumps is the &ldquo, W , Z scale functions paradigm&rdquo, by which the knowledge of the scale functions W , Z extends immediately to other risk control problems. The same is true largely for strong Markov processes X t , with the notable distinctions that (a) it is more convenient to use as &ldquo, basis&rdquo, differential exit functions &nu, &delta, and that (b) it is not yet known how to compute &nu, or W , Z beyond the L&eacute, vy, diffusion, and a few other cases. The unifying framework outlined in this paper suggests, however, via an example that the spectrally negative Markov and L&eacute, vy cases are very similar (except for the level of work involved in computing the basic functions &nu, ). We illustrate the potential of the unified framework by introducing a new objective () for the optimization of dividends, inspired by the de Finetti problem of maximizing expected discounted cumulative dividends until ruin, where we replace ruin with an optimally chosen Azema-Yor/generalized draw-down/regret/trailing stopping time. This is defined as a hitting time of the &ldquo, draw-down&rdquo, process Y t = sup 0 &le, s &le, t X s - X t obtained by reflecting X t at its maximum. This new variational problem has been solved in a parallel paper.

In this paper, we consider fault-tolerant resolving sets in graphs. We characterize n-vertex graphs with fault-tolerant metric dimension n, n &minus, 1 , and 2, which are the lower and upper extremal cases. Furthermore, in the first part of the paper, a method is presented to locate fault-tolerant resolving sets by using classical resolving sets in graphs. The second part of the paper applies the proposed method to three infinite families of regular graphs and locates certain fault-tolerant resolving sets. By accumulating the obtained results with some known results in the literature, we present certain lower and upper bounds on the fault-tolerant metric dimension of these families of graphs. As a byproduct, it is shown that these families of graphs preserve a constant fault-tolerant resolvability structure.

The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif., Comment: 27 pages, full version of the paper accepted to ICALP 2019

Collatz Conjecture (3x+1 problem) states any natural number x will return to 1 after 3⁎x+1 computation (when x is odd) and x/2 computation (when x is even). In this paper, we propose a new approach for possibly proving Collatz Conjecture (CC). We propose Reduced Collatz Conjecture (RCC)—any natural number x will return to an integer that is less than x. We prove that RCC is equivalent to CC. For proving RCC, we propose exploring laws of Reduced Collatz Dynamics (RCD), i.e., from a starting integer to the first integer less than the starting integer. RCC can also be stated as follows: RCD of any natural number exists. We prove that RCD is the components of original Collatz dynamics (from a starting integer to 1); i.e., RCD is more primitive and presents better properties. We prove that RCD presents unified structure in terms of (3⁎x+1)/2 and x/2, because 3⁎x+1 is always followed by x/2. The number of forthcoming (3⁎x+1)/2 computations can be determined directly by inputting x. We propose an induction method for proving RCC. We also discover that some starting integers present RCD with short lengths no more than 7. Hence, partial natural numbers are proved to guarantee RCC in this paper, e.g., 0 module 2; 1 module 4; 3 module 16; 11 or 23 module 32; 7, 15, or 59 module 128. The future work for proving CC can follow this direction, to prove that RCD of left portion of natural numbers exists.