Search

A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists, even if all vertical segments have unit length. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions., Discrete Mathematics & Theoretical Computer Science ; Vol. 21 no. 3 ; 1365-8050

In this paper, it is explicitly determined the r-dynamic chromatic number of the direct product of any given path with either a complete graph or a wheel graph. Illustrative examples are shown for each one of the cases that are studied throughout the paper. Junta de Andalucía FQM-016

This survey is a slightly extended version of the lecture given by the author at the \emph{VI International Course of Mathematical Analysis in Andaluc\'\i a} (CIDAMA), in September 2014. Most results are contained (in a slightly less general setting) in the earlier paper [3] (Garrig\'os, Hartzstein, Signes, Torrea and Viviani, Pointwise convergence to initial data of heat and Laplace equations, Trans. Amer. Math. Soc. 368 (9) (2016), 6575-6600)., Comment: 17 pages. This is a preprint version of survey paper published in Advanced courses of mathematical analysis VI, 153-171, World Sci. Publ., Hackensack, NJ, 2017

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2+ε. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1+ε, and then solve its resulting instances up to a factor of 2+ε by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.

This paper deals with 1) angle trisection, 2) Bhaskara’s first proof, and 3) Pythagorean theorem. The purpose of this paper is threefold. First, to show a new, direct method of trisecting the 900 angle using unmarked straight edge and compass; secondly, to show Bhaskara’s first proof of the Pythagorean theorem (c2 = a2 + b2) as embedded in this new, direct trisection of the 900 angle; lastly, to show the derivation of the Pythagorean theorem from this trisection of the 900 angle. This paper employs the direct dissection method. It concludes by presenting four points: a) the concept of trisectability as distinct from concept of constructability; b) the trisection of the 900 angle as really a new, different method; c) Bhaskara’s first proof of the Pythagorean theorem as truly embedded in this trisection of the 900 angle and; d) another way of deriving Pythagorean theorem from this trisection of the 900 angle.

Covering rough set is a classical generalization of rough set. As covering rough set is a mathematical tool to deal with incomplete and incomplete data, it has been widely used in various fields. The aim of this paper is to extend the covering rough sets to interval neutrosophic sets, which can make multi-attribute decision making problem more tractable. Interval neutrosophic covering rough sets can be viewed as the bridge connecting Interval neutrosophic sets and covering rough sets. Firstly, the paper introduces the definition of interval neutrosophic sets and covering rough sets, where the covering rough set is defined by neighborhood. Secondly, Some basic properties and operation rules of interval neutrosophic sets and covering rough sets are discussed. Thirdly, the definition of interval neutrosophic covering rough sets are proposed. Then, some theorems are put forward and their proofs of interval neutrosophic covering rough sets also be gived. Lastly, this paper gives a numerical example to apply the interval neutrosophic covering rough sets.

This paper addresses the $\mathcal {H}_{2}$ , $\mathcal {H}_\infty $ and mixed $\mathcal {H}_{2}/\mathcal {H}_\infty $ formation static output control of continuous-time linear multi-agent systems with Markovian switching network topologies. It is assumed that the operation mode of the network topology cannot be directly measured but, instead, can be estimated by an imperfect detector. To model this problem, we consider a continuous-time hidden Markov model, in which the hidden component represents the real operation mode of the network topology while the observed component represents the information emitted from the detector and available for the controller. It is also assumed that only a partial information from the state variables of the multi-agent systems is available. By using an LMI (linear matrix inequality) formulation, a distributed static output controller which switches according to the detector information is designed to guarantee the stability in the mean square sense of the closed loop system, as well as an upper-bound for an index performance. Three situations are considered for the performance criteria: the $\mathcal {H}_{2}$ norm, the $\mathcal {H}_\infty $ norm, and the mixed $\mathcal {H}_{2}/\mathcal {H}_\infty $ norms. The paper is concluded with a numerical example to illustrate the effectiveness of the theoretical results.

This paper considers the problem of expanding a language class that can be proven by a non-interactive zero-knowledge proof system (NIZK) in a black-box manner in the common reference string model. Namely, given NIZKs for two languages, ${\mathcal L}_{0}$ and ${\mathcal L}_{1}$ , can we construct an NIZK for ${\mathcal L}_{0} \vee {\mathcal L} _{1}$ in a black-box manner? NIZKs for disjunctive languages have a large number of applications, such as electronic voting. Therefore, such a black-box construction may enable the efficient constructions of such applications. However, Abe et al. (PKC 2020) showed that this is impossible if the two given NIZKs are simulation-sound. In this paper, we prove that it is also impossible if the two given NIZKs are constructed by the commit-and-prove methodology that is typically used in many cryptographic protocols, including NIZKs. This result suggests that if we want to augment the capability of NIZKs in terms of the languages they can prove, we should rely on certain properties or structures of the underlying NIZKs, such as algebraic structures.

Rockburst is a typical engineering geological disaster under the condition of high geostress. The rockburst classification and prediction are of great significance for the prevention and control of engineering geological disasters under the high geostress environment, and can reduce or even avoid the loss of personnel, equipment, and property. Thus, the GA-XGB model for rockburst classification prediction is proposed in this paper. Specifically, the parameter search process of extreme gradient boosting (XGB) is optimized based on the genetic algorithm (GA), and 10-fold cross-validation is performed on the Dataset collected from literature research. There are 275 sets of complete data, including 6 parameters: $\sigma _{\theta }$ , $\sigma _{\mathrm {c}}$ , $\sigma _{\mathrm {t}}$ , $\sigma _{\theta }/\sigma _{\mathrm {c}}$ , $\sigma _{\mathrm {c}}/\sigma _{\mathrm {t}}$ and $\text{W}_{\mathrm {et}}$ . Afterward, the impact of different indicator parameter combinations on the performance of the proposed model is explored and compared to existing machine learning models (such as SVM and XGB). Finally, the classification evaluation indexes (precision, recall, and F1 score) are calculated and compared to those obtained by several other algorithms. The results indicate that the method proposed in this paper performs better than other machine algorithms such as XGB, SVM, DT, and Bayes.

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.

As stated in (7), binary coded computer programs can be shown as a metric space. Therefore, they can be measured by metric in a sense of metric space theory. This paper presents the proof that Fréchet metric is a metric on the space of all sequences of elements M={0,1t} Therefore, it is usable to build a system of software metrics based on the metric space theory

In this paper, we consider a class of transportation problems which arises in sample surveys and other areas of statistics. The associated cost matrices of these transportation problems are of special structure. We observe that the optimality of North West corner solution holds for the general problem where cost component is replaced by a convex function. We revisit assignment problem and present a weighted version of K$\ddot{\mbox{o}}$nig-Egerv$\acute{\mbox{a}}$ry theorem and Hungarian method. The weighted Hungarian method proposed in the paper can be used for solving transportation problem.

Lattice-based cryptographic scheme is constructed based on hard problems on a lattice such as the short integer solution (SIS) problem and the learning with error (LWE). However, the cryptographic scheme based on SIS or LWE is inefficient since the size of the key is too large. Thus, most cryptographic schemes use the variants of LWE and SIS with ring and module structures. Albrecht and Deo showed that there is a reduction from module-LWE (M-LWE) to ring-LWE (R-LWE) in the polynomial ring by handling the error rate and modulus. However, unlike the LWE problem, the SIS problem does not have an error rate, but there is the upper bound β on the norm of the solution of the SIS problem. In this paper, we propose the two novel reductions related to module-SIS (M-SIS) and ring-SIS (R-SIS) on a polynomial ring. We propose (i) the reduction from R-SIS qk,mk,βk to R-SISq,m,β and (ii) the reduction from M-SIS to R-SIS under norm constraint of R-SIS. Combining these two results implies that R-SIS for a specified modulus and number samples is more difficult than M-SIS under norm constraints of R-SIS, which provides the range of possible module ranks for M-SIS. From the reduction we propose, contrary to the widely known belief, our result shows that there is a possibility that the security parameters of M-SIS may be less secure when it reduces to R-SIS for the theoretical reasons presented in this paper. Therefore, when generating parameters on an M-SIS structure, the theoretical security level over R-SIS also should also be checked at the same time.

Given a set $A$ of $n$ people and a set $B$ of $m \geq n$ items, with each person having a list that ranks his/her preferred items in order of preference, we want to match every person with a unique item. A matching $M$ is called popular if for any other matching $M'$, the number of people who prefer $M$ to $M'$ is not less than the number of those who prefer $M'$ to $M$. For given $n$ and $m$, consider the probability of existence of a popular matching when each person's preference list is independently and uniformly generated at random. Previously, Mahdian showed that when people's preference lists are strict (containing no ties) and complete (containing all items in $B$), if $\alpha = m/n > \alpha_*$, where $\alpha_* \approx 1.42$ is the root of equation $x^2 = e^{1/x}$, then a popular matching exists with probability $1-o(1)$; and if $\alpha < \alpha_*$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at $\alpha_*$. In this paper, we investigate phase transitions in the case that people's preference lists are strict but not complete. We show that in the case where every person has a preference list with length of a constant $k \geq 4$, a similar phase transition occurs at $\alpha_k$, where $\alpha_k \geq 1$ is the root of equation $x e^{-1/2x} = 1-(1-e^{-1/x})^{k-1}$., Comment: A shortened version of this paper has appeared at WALCOM 2018

In this paper, we first address the dynamics of the elegant multi-valued quaternionic Hopfield neural network (MV-QHNN) proposed by Minemoto and collaborators. Contrary to what was expected, we show that the MV-QHNN, as well as one of its variation, does not always come to rest at an equilibrium state under the usual conditions. In fact, we provide simple examples in which the network yields a periodic sequence of quaternionic state vectors. Afterward, we turn our attention to the continuous-valued quaternionic Hopfield neural network (CV-QHNN), which can be derived from the MV-QHNN by means of a limit process. The CV-QHNN can be implemented more easily than the MV-QHNN model. Furthermore, the asynchronous CV-QHNN always settles down into an equilibrium state under the usual conditions. Theoretical issues are all illustrated by examples in this paper.

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties.

Linear complexity is an important property to measure the unpredictability of pseudo-random sequences. Trace representation is helpful for analyzing cryptography properties of pseudo-random sequences. In this paper, a class of new Ding generalized cyclotomic binary sequences of order two with period pq is constructed based on the new segmentation of Ding Helleseth generalized cyclotomy. Firstly, the linear complexity and minimal polynomial of the sequences are investigated. Then, their trace representation is given. It is proved that the sequences have larger linear complexity and can resist the attack of the Berlekamp–Massey algorithm. This paper also confirms that generalized cyclotomic sequences with good randomness may be obtained by modifying the characteristic set of generalized cyclotomy.

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

In the present paper, we construct quantum Markov chains (QMC) over the Comb graphs. As an application of this construction, it is proved the existence of the disordered phase for the Ising type models (within QMC scheme) over the Comb graphs. Moreover, it is also established that the associated QMC has clustering property with respect to translations of the graph. We stress that this paper is the first one where a nontrivial example of QMC over non-regular graphs is given.

© 2021. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ This paper provides a classification of all monotonic bipartite simple games. The problem we deal with is very versatile since simple games are inequivalent monotonic Boolean functions, functions that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making. The obtained classification can be implemented in an algorithm able to enumerate bipartite simple games. These numbers provide some light on enumerations of several subclasses of bipartite simple games, for which we find formulas. Complete simple games, a subclass of all simple games for which the desirability relation is a complete preordering, were already classified by means of two parameters: a vector and a matrix fulfilling some conditions. Complete simple games are inequivalent monotonic regular Boolean functions. In this paper, we deduce a procedure for bipartite non-complete games, which allows enumerating the number of bipartite simple games. Several formulas are obtained, in particular polynomial expressions for the number of bicameral meet games and the number of bicameral join games, two types of voting systems widely used in practice. This research has been partially supported by funds from the Ministry of Science, Innovation and Universities grant PID2019-104987GB-I00.

The energy of a graph is defined as the sum of the absolute values of its eigenvalues. Recently, there has been a lot of interest in graph energy research. Previous literature has suggested integrating energy, Laplacian energy, and signless Laplacian energy with single-valued neutrosophic graphs (SVNGs). This integration is used to solve problems that are characterized by indeterminate and inconsistent information. However, when the information is endowed with both positive and negative uncertainty, then bipolar single-valued neutrosophic sets (BSVNs) constitute an appropriate knowledge representation of this framework. A BSVNs is a generalized bipolar fuzzy structure that deals with positive and negative uncertainty in real-life problems with a larger domain. In contrast to the previous study, which directly used truth and indeterminate and false membership, this paper proposes integrating energy, Laplacian energy, and signless Laplacian energy with BSVNs to graph structure considering the positive and negative membership degree to greatly improve decisions in certain problems. Moreover, this paper intends to elaborate on characteristics of eigenvalues, upper and lower bound of energy, Laplacian energy, and signless Laplacian energy. We introduced the concept of a bipolar single-valued neutrosophic graph (BSVNG) for an energy graph and discussed its relevant ideas with the help of examples. Furthermore, the significance of using bipolar concepts over non-bipolar concepts is compared numerically. Finally, the application of energy, Laplacian energy, and signless Laplacian energy in BSVNG are demonstrated in selecting renewable energy sources, while optimal selection is suggested to illustrate the proposed method. This indicates the usefulness and practicality of this proposed approach in real life.

This paper revisits the connection between the girth of a protograph-based LDPC code given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose in order to obtain the necessary and sufficient conditions for a code to have given girth between 6 and 12, and to show how these conditions can be incorporated into simple algorithms to construct codes of that girth. To this end, we highlight the role that certain submatrices that appear in these products have in the construction of codes of desired girth. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square submatrix obtained from it and we show how this equivalence is particularly strong for a protograph based parity-check matrix of variable node degree 2, where the cycles in its Tanner graph correspond one-to-one to the cycles in the Tanner graph of a square submatrix obtained by adding the permutation matrices (or products of these) in the composition of the parity-check matrix. We end the paper with exemplary constructions of codes with various girths and computer simulations. Although, we mostly assume the case of fully connected protographs of variable node degree 2 and 3, the results can be used for any parity-check matrix/protograph-based Tanner graph., Submitted to the 2021 IEEE International Symposium on Information Theory

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.

Noncatastrophic encoders are an important class of polynomial generator matrices of convolutional codes. When these polynomials have coefficients in a finite field, these encoders have been characterized are being polynomial left prime matrices. In this paper we study the notion of noncatastrophicity in the context of convolutional codes when the polynomial matrices have entries in a finite ring. In particular, we need to introduce two different notion of primeness in order to fully characterize noncatastrophic encoders over the finite ring Z_{p^r}. The second part of the paper is devoted to investigate the notion of free and column distance in this context when the convolutional code is a free finitely generated Z_{p^r}-module. We introduce the notion of b-degree and provide new bounds on the free distances and column distance. We show that this class of convolutional codes is optimal with respect to the column distance and to the free distance if and only if its projection on Z_p is., 17 pages

Given n points in d -dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d = 2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.

The Thue-Morse set T is the set of those non-negative integers whose binary expansions have an even number of 1. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word abbabaabbaababba..., which is the fixed point starting with a of the word morphism sending a to ab and b to ba. The numbers in T are sometimes called the evil numbers. We obtain an exact formula for the state complexity (i.e. the number of states of its minimal automaton) of the multiplication by a constant of the Thue-Morse set with respect to any integer base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set mT for any positive integers m and p. The used method is general for any b-recognizable set of integers. As an application, we obtain a decision procedure running in quadratic time for the problem of deciding whether a given 2^p-recognizable set is equal to some multiple of the Thue-Morse set., In Proceedings GandALF 2019, arXiv:1909.05979. Short paper. A full version of this paper appears as arXiv:1903.06114

In the paper we describe a new propositional encoding procedure for the property that all objects comprising some finite set are distinct. For the considered class of combinatorial problems it is sufficient to represent the elements of such set by their natural numbers. Thus, there is a problem of constructing a satisfiable Boolean formula, the satisfying assignments of which encode the first $n$ natural numbers without taking into account their order. The necessity to encode such sets into Boolean logic is motivated by the desire to apply to the corresponding combinatorial problems the state-of-the-art algorithms for solving the Boolean satisfiability problem (SAT). In the paper we propose the new approach to defining the Boolean formula for the characteristic function of the predicate which takes the value of True only on the sets of binary words encoding the numbers from 0 to $n-1$. The corresponding predicate was named OtO (from One-to-One). The propositional encoding of the OtO-predicate has a better lower bound compared to the propositional encoding of a relatively similar predicate known as OOC-predicate (from Only One Cardinality). The proposed OtO-predicate is used to reduce to SAT a number of problems related to Latin squares. In particular, using the OtO-predicate we constructed the SAT encodings for the problems of finding orthogonal pairs and quasi-orthogonal triples of Latin squares of order 10. We used the multi-threaded SAT solvers and the resources of a computing cluster to solve these problems.

In this paper we consider Susceptible \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rightarrow $$\end{document}→ Infectious \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rightarrow $$\end{document}→ Recovered (SIR) epidemics on random graphs with clustering. To incorporate group structure of the underlying social network, we use a generalized version of the configuration model in which each node is a member of a specified number of triangles. SIR epidemics on this type of graph have earlier been investigated under the assumption of homogeneous infectivity and also under the assumption of Poisson transmission and recovery rates. We extend known results from literature by relaxing the assumption of homogeneous infectivity both in individual infectivity and between different kinds of neighbours. An important special case of the epidemic model analysed in this paper is epidemics in continuous time with arbitrary infectious period distribution. We use branching process approximations of the spread of the disease to provide expressions for the basic reproduction number \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_0$$\end{document}R0, the probability of a major outbreak and the expected final size. In addition, the impact of random vaccination with a perfect vaccine on the final outcome of the epidemic is investigated. We find that, for this particular model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_0$$\end{document}R0 equals the perfect vaccine-associated reproduction number. Generalizations to groups larger than three are discussed briefly.

Although quantum maximal-distance-separable (MDS) codes that satisfy the quantum singleton bound have become an important research topic in the quantum coding theory, it is not an easy task to search for quantum MDS codes with the minimum distance that is larger than (q/2) + 1. The pre-shared entanglement between the sender and the receiver can improve the minimum distance of quantum MDS codes such that the minimum distance of some constructed codes achieves (q/2) + 1 or exceeds (q/2) + 1. Meanwhile, how to determine the required number of maximally entangled states to make the minimum distance of quantum MDS codes larger than (q/2) + 1 is an interesting problem in the quantum coding theory. In this paper, we utilize the decomposition of the defining set and q2-cyclotomic cosets of constacyclic codes with the form q = αm + t or q = αm + α - t and n = (q2 + 1/α) to construct some new families of entanglement-assisted quantum MDS codes that satisfy the entanglement-assisted quantum singleton bound, where q is an odd prime power and m is a positive integer, while both α and t are positive integers such that α = t2 + 1. The parameters of these codes constructed in this paper are more general compared with the ones in the literature. Moreover, the minimum distance of some codes in this paper is larger than (q/2) + 1 or q + 1.

Subject of Research.The paper considers simulation model of the electro generating installation based on photovoltaic converters. It is known that photovoltaic cells have rather low conversion efficiency of energy therefore performance improving of the designed energy system can be partially reached by means of controlled intermediate converters. The main goal of this paper is model implementation of a solar power system and also comparative analysis of the different maximum power point tracking algorithms which are used to control energy system with the purpose to increase power efficiency of all system. Method. All algorithms considered in the paper are based on the search for an extremum on the volt-power characteristic of a photovoltaic converter. Implementation of the most popular methods of maximum power point tracking is considered: "Perturbation and observation" and "Increasing conductivity". An algorithm based on the theory of fuzzy logic is proposed for application aimed at the growth of photovoltaic cells efficiency as an alternative method for traditional algorithms. Main Results. The model of solar panel control system is implemented in MATLAB/Simulink. Three methods for maximum power point tracking within this photovoltaic system are considered and implemented. Comparative analysis of operation of different control algorithms is carried out for different levels of solar radiation intensity. Practical Relevance. The algorithms can be implemented in real power systems for improvement of their overall performance.

P-time event graphs (P-TEGs) are specific timed discrete-event systems, in which the timing of events is constrained by intervals. An important problem is to check, for all natural numbers $d$, the existence of consistent $d$-periodic trajectories for a given P-TEG. In graph theory, the Proportional-Inverse-Constant-Non-positive Circuit weight Problem (PIC-NCP) consists in finding all the values of a parameter such that a particular parametric weighted directed graph does not contain circuits with positive weight. In a related paper, we have proposed a strongly polynomial algorithm that solves the PIC-NCP in lower worst-case complexity compared to other algorithms reported in literature. In the present paper, we show that the first problem can be formulated as an instance of the second; consequently, we prove that the same algorithm can be used to find $d$-periodic trajectories in P-TEGs. Moreover, exploiting the connection between the PIC-NCP and max-plus algebra we prove that, given a P-TEG, the existence of a consistent 1-periodic trajectory of a certain period is a necessary and sufficient condition for the existence of a consistent $d$-periodic trajectory of the same period, for any value of $d$., Minor corrections

In this paper we deal with polar code automorphisms that are beneficial under low-latency automorphism ensemble (AE) decoding, and we propose polar code designs that have such automorphisms. Successive-cancellation (SC) decoding and thus SC-based AE decoding are invariant with respect to the only known polar code automorphisms, namely those of the lower-triangular affine (LTA) group. To overcome this problem, we provide methods to determine whether a given polar code has non-LTA automorphisms and to identify such automorphisms. Building on this, we design specific polar codes that admit automorphisms in the upper-diagonal linear (UTL) group, and thus render SC-based AE decoding effective. Demonstrated by examples, these new polar codes under AE decoding outperform conventional polar codes under SC list decoding in terms of error rate, while keeping the latency comparable to SC decoding. Moreover, state-of-the-art BP-based permutation decoding for polar codes is beaten by BP-based AE thanks to this design., 6 pages, 4 figures, final version of conference paper accepted to IEEE ITW 2021

A semitotal dominating set S (abbreviated semi-TD-set) of graph G = (V, E) is a subset such that S is a dominating set and each vertex in the S is within 2 distance from the another vertex of S. The semitotal domination number, denoted by ?t2(G), is the minimum cardinality taken over all semitotal dominating sets of G. In this paper, we examine the semitotal domination number of graphs obtained by some graph operations such as corona, join, modular product, and lexicographic product. © 2021 Wiley Periodicals LLC, Ege Üniversitesi: FDK?2018?20266, The author is thankful to the editors and the anonymous reviewers for their valuable comments. This paper is supported by Ege University PhD Scientific Research Project (BAP) under project number FDK?2018?20266.

It is conjectured that within the class group of any number field, for every integer $\ell \geq 1$, the $\ell$-torsion subgroup is very small (in an appropriate sense, relative to the discriminant of the field). In nearly all settings, the full strength of this conjecture remains open, and even partial progress is limited. Significant recent progress toward average versions of the $\ell$-torsion conjecture has crucially relied on counts for number fields, raising interest in how these two types of question relate. In this paper we make explicit the quantitative relationships between the $\ell$-torsion conjecture and other well-known conjectures: the Cohen-Lenstra heuristics, counts for number fields of fixed discriminant, counts for number fields of bounded discriminant (or related invariants), and counts for elliptic curves with fixed conductor. All of these considerations reinforce that we expect the $\ell$-torsion conjecture is true, despite limited progress toward it. Our perspective focuses on the relation between pointwise bounds, averages, and higher moments, and demonstrates the broad utility of the "method of moments.", The paper arXiv:1709.09637v1 by the same authors was submitted for publication in a significantly shorter version; some of the excluded material appears in this new paper, which also proves further results. Version 2 updates some references, with corresponding improvements in Section 6. Version 3 has a few small changes to streamline exposition after referee process

In this present paper, we introduce the idea and concept of n-polynomial s-type preinvex functions. We elaborate and investigate the algebraic properties of the newly introduced definition and discuss their connections and relations with convex functions. We find the new sort of Hermite-Hadamard inequality via a newly introduced definition. Furthermore, some refinements of Hermite-Hadamard inequality are given. Finally, we investigated some applications via this newly introduced definition. The results obtained in this paper can be viewed as significant improvement of previously known results. H.E.C. Pakistan under NRPU project [7906] The research of the author Saad Ihsan Butt has been fully supported by H.E.C. Pakistan under NRPU project 7906. WOS:000649589100001 2-s2.0-85105631491

This work is dedicated to APN and AB functions which are optimal against differential and linear cryptanlysis when used as Sboxes in block ciphers. They also have numerous applications in other branches of mathematics and information theory such as coding theory, sequence design, combinatorics, algebra and projective geometry. In this paper we give an overview of known constructions of APN and AB functions, in particular, those leading to infinite classes of these functions. Among them, the bivariate construction method, the idea first introduced in 2011 by the third author of the present paper, turned out to be one of the most fruitful. It has been known since 2011 that one of the families derived from the bivariate construction contains the infinite families derived by Dillon’s hexanomial method. Whether the former family is larger than the ones it contains has stayed an open problem which we solve in this paper. Further we consider the general bivariate construction from 2013 by the third author and study its relation to the recently found infinite families of bivariate APN functions.

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.

In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph $G=(V,E)$, an oriented $r$-coloring for $G$ is a partition of the vertex set $V$ into $r$ independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of $G$ is the smallest integer $r$ such that $G$ permits an oriented $r$-coloring. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of $7$ for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure, 25 pages. arXiv admin note: text overlap with arXiv:2006.13911

This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

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.