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.

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 traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document}G=(V,E) and non-negative distances d for every edge, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is a branch and cut approach. Usually the integrality constraints are relaxed first and all separation processes to identify violated inequalities are done on fractional solutions. In our approach we try to exploit the impressive performance of current ILP-solvers and work only with integer solutions without ever interfering with fractional solutions. We stick to a very simple ILP-model and relax the subtour elimination constraints only. The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible. These attempts are based on the clustering of vertices with additional insights gained from empirical observations and random graph theory. Computational results are performed on test instances taken from the TSPLIB95 and on random Euclidean graphs.

The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to multi-graphs (or equivalently, weighted graphs). In this short paper we rule out the possibility of such an extension by showing that there are multi-graphs with only n^{2+o(1)} triangles that are still far from being triangle-free. On the other hand, we show that for some g(n)=\omega(1), if a multi-graph (or weighted graph) has only g(n)n^2 triangles then it must be close to being triangle-free. The proof relies on variants of the Ruzsa-Szemer\'edi theorem.

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

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.

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

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

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.

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

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

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

The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an integral base-polyhedron. A fundamental difference between the fractional and the discrete case is that a base-polyhedron has always a unique dec-min element, while the set of dec-min elements of an M-convex set admits a rich structure, described here with the help of a "canonical chain". As a consequence, we prove that this set arises from a matroid by translating the characteristic vectors of its bases with an integral vector. By relying on these characterizations, we prove that an element is dec-min if and only if the square-sum of its components is minimum, a property resulting in a new type of min-max theorems. The characterizations also give rise, as shown in the companion paper, to a strongly polynomial algorithm, and to several applications in the areas of resource allocation, network flow, matroid, and graph orientation problems, which actually provided a major motivation to the present investigations. In particular, we prove a conjecture on graph orientation., 39 pages This is a revised version of the first half of "A. Frank and K. Murota; Discrete decreasing minimization, PartI: Base-polyhedra with applications in network optimization" arXiv:1808.07600

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.

The interpretability logic of a mathematical theory describes the structural behavior of interpretations over that theory. Different theories have different logics. This paper from 2011 revolves around the question what logic describes the behavior that is present in all theories with a minimum amount of arithmetic; the intersection over all such theories so to say. We denote this target logic by ${\textbf{IL}}({\rm All})$. In this paper we present a new principle $\sf R$ in ${\textbf{IL}}({\rm All})$. We show that $\sf R$ does not follow from the logic ${\textbf{IL}}{\sf P_0W^*}$ that contains all previously known principles. This is done by providing a modal incompleteness proof of ${\textbf{IL}}{\sf P_0W^*}$: showing that $\sf R$ follows semantically but not syntactically from ${\textbf{IL}}{\sf P_0W^*}$. Apart from giving the incompleteness proof by elementary methods, we also sketch how to work with so-called Generalized Veltman Semantics as to establish incompleteness. To this extent, a new version of this Generalized Veltman Semantics is defined and studied. Moreover, for the important principles the frame correspondences are calculated. After the modal results it is shown that the new principle $\sf R$ is indeed valid in any arithmetically theory. The proof employs some elementary results on definable cuts in arithmetical theories.

Given a 3-colorable graph X , the 3-coloring complex B ( X ) is the graph whose vertices are all the independent sets which occur as color classes in some 3-coloring of X . Two color classes C , D ∈ V ( B ( X ) ) are joined by an edge if C and D appear together in a 3-coloring of X . The graph B ( X ) is 3-colorable. Graphs for which B ( B ( X ) ) is isomorphic to X are termed reflexive graphs. In this paper, we consider 3-edge-colorings of cubic graphs for which we allow half-edges. Then we consider the 3-coloring complexes of their line graphs. The main result of this paper is a surprising outcome that the line graph of any connected cubic triangle-free outerplanar graph is reflexive. We also exhibit some other interesting classes of reflexive line graphs.

In this paper, we describe the structure of finite groups whose element orders or proper (abelian) subgroup orders form an arithmetic progression of ratio [Formula: see text]. This extends the case [Formula: see text] studied in previous papers [R. Brandl and W. Shi, Finite groups whose element orders are consecutive integers, J. Algebra 143 (1991) 388–400; Y. Feng, Finite groups whose abelian subgroup orders are consecutive integers, J. Math. Res. Exp. 18 (1998) 503–506; W. Shi, Finite groups whose proper subgroup orders are consecutive integers, J. Math. Res. Exp. 14 (1994) 165–166].

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

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

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

This paper concerns the Vertex Reinforced Jump Process (VRJP) and its representations as a Markov process in random environment. In [21], it was shown that the VRJP on finite graphs, under a certain time rescaling, has the distribution of a mixture of Markov jump processes. This representation was extended to infinite graphs in [23], by introducing a random potential $\beta $. In this paper, we show that all possible representations of the VRJP as a mixture of Markov processes can be expressed in a similar form as in [23], using the random field $\beta $ and harmonic functions for an associated operator $H_\beta $. This allows to show that the VRJP on $\mathbb {Z}^{d}$ (with certain initial conditions) has a unique representation, by proving that an associated Martin boundary is trivial. Moreover, on infinite trees, we construct a family of representations, that are all different when the VRJP is transient and the tree is $d$-regular (with $d\geq 3$).

In this paper, we give a geometric characterization of minimal linear codes. In particular, we relate minimal linear codes to cutting blocking sets, introduced in a recent paper by Bonini and Borello. Using this characterization, we derive some bounds on the length and the distance of minimal codes, according to their dimension and the underlying field size. Furthermore, we show that the family of minimal codes is asymptotically good. Finally, we provide some geometrical constructions of minimal codes., Comment: 22 pages

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

In 1975 Barwise and Schlipf published a landmark paper whose main theorem asserts that a nonstandard model $\mathcal{M}$ of PA (Peano arithmetic) is recursively saturated iff $\mathcal{M}$ has an expansion that satisfies the subsystem $\Delta_1^1$-${\sf CA}_0$ of second order arithmetic. In this paper we identify a crucial error in the Barwise-Schlipf proof of the right-to-left direction of the theorem, and additionally, we offer a correct proof of the problematic direction., Comment: Some editorial changes have been made. To appear in PAMS

This paper is focused on derivations of data-processing and majorization inequalities for $f$-divergences, and their applications in information theory and statistics. For the accessibility of the material, the main results are first introduced without proofs, followed by exemplifications of the theorems with further related analytical results, interpretations, and information-theoretic applications. One application refers to the performance analysis of list decoding with either fixed or variable list sizes; some earlier bounds on the list decoding error probability are reproduced in a unified way, and new bounds are obtained and exemplified numerically. Another application is related to a study of the quality of approximating a probability mass function, induced by the leaves of a Tunstall tree, by an equiprobable distribution. The compression rates of finite-length Tunstall codes are further analyzed for asserting their closeness to the Shannon entropy of a memoryless and stationary discrete source. Almost all the analysis is relegated to the appendices, which form a major part of this manuscript., This paper is published in the Entropy journal, vol. 21, no. 10, paper 1022, pages 1-80, October 21, 2019 (https://www.mdpi.com/1099-4300/21/10/1022)

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

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

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

The expected running time of the classical (1+1) EA on the OneMax benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of $O((\log n)/n)$. The same approach proposed there also leads to a full asymptotic expansion with errors of the form $O(n^{-K}\log n)$ for any $K>0$. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on OneMax and obtains that the expected running time $E(T)$, starting from $\lceil n/2\rceil$ one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely $$\sum_{k=1}^{\lfloor n/2\rfloor}\frac{1}{\Delta(k)} - c_1\log n \le E(T) \le \sum_{k=1}^{\lfloor n/2\rfloor}\frac{1}{\Delta(k)} - c_2\log n,$$ where $\Delta(k)$ is the drift (expected increase of the number of one-bits from the state of $n-k$ ones) and $c_1,c_2 >0$ are explicitly computed constants. This improves the previous asymptotic error known for the sum of inverse drifts from $\tilde{O}(n^{2/3})$ to a logarithmic error and gives for the first time a non-asymptotic error bound. Using standard asymptotic techniques, the difference between $E(T)$ and the sum of inverse drifts is found to be $(e/2)\log n+O(1)$., Comment: 33 pages; preprint of a paper that will be published in the proceedings of FOGA 2019; v2: minor corrections

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

The number of real roots has been a central subject in the theory of random polynomials and random functions since the fundamental papers of Littlewood-Offord and Kac in the 1940s. The main task here is to determine the limiting distribution of this random variable. In 1974, Maslova famously proved a central limit theorem (CLT) for the number of real roots of Kac polynomials. It has remained the only limiting theorem available for the number of real roots for more than four decades. In this paper, using a new approach, we derive a general CLT for the number of real roots of a large class of random polynomials with coefficients growing polynomially. Our result both generalizes and strengthens Maslova's theorem., some references were added and several proofs were elaborated

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

This is a follow-up to a paper with the same title and by the same authors. In that paper, all groups were assumed to be abelian, and we are now aiming to generalize the results to nonabelian groups. The motivating point is Pedersen's theorem, which does hold for an arbitrary locally compact group $G$, saying that two actions $(A,\alpha)$ and $(B,\beta)$ of $G$ are outer conjugate if and only if the dual coactions $(A\rtimes_{\alpha}G,\widehat\alpha)$ and $(B\rtimes_{\beta}G,\widehat\beta)$ of $G$ are conjugate via an isomorphism that maps the image of $A$ onto the image of $B$ (inside the multiplier algebras of the respective crossed products). We do not know of any examples of a pair of non-outer-conjugate actions such that their dual coactions are conjugate, and our interest is therefore exploring the necessity of latter condition involving the images, and we have decided to use the term "Pedersen rigid" for cases where this condition is indeed redundant. There is also a related problem, concerning the possibility of a so-called equivariant coaction having a unique generalized fixed-point algebra, that we call "fixed-point rigidity". In particular, if the dual coaction of an action is fixed-point rigid, then the action itself is Pedersen rigid, and no example of non-fixed-point-rigid coaction is known., Comment: Minor revision. To appear in Internat. J. Math

Total correlation (`TC') and dual total correlation (`DTC') are two classical ways to quantify the correlation among an $n$-tuple of random variables. They both reduce to mutual information when $n=2$. The first part of this paper sets up the theory of TC and DTC for general random variables, not necessarily finite-valued. This generality has not been exposed in the literature before. The second part considers the structural implications when a joint distribution $\mu$ has small TC or DTC. If $\mathrm{TC}(\mu) = o(n)$, then $\mu$ is close to a product measure according to a suitable transportation metric: this follows directly from Marton's classical transportation-entropy inequality. If $\mathrm{DTC}(\mu) = o(n)$, then the structural consequence is more complicated: $\mu$ is a mixture of a controlled number of terms, most of them close to product measures in the transportation metric. This is the main new result of the paper., Comment: 39 pages [v2:] Slight changes in presentation based on feedback from colleagues [v3, v4:] Small revisions during preparation for journal

A formula for the modular data of $\mathcal{Z}(Vec^{\omega}G)$ was given by Coste, Gannon and Ruelle in arXiv:hep-th/0001158, but without an explicit proof for arbitrary 3-cocycles. This paper presents a derivation using the representation category of the quasi Hopf algebra $D^{\omega}G$. Further, we have written code to compute this modular data for many pairs of small finite groups and 3-cocycles. This code is optimised using Galois symmetries of the S and T matrices. We have posted a database of modular data for the Drinfeld center of every Morita equivalence class of pointed fusion categories of dimension less than 64., Comment: 28 pages, 4 figures, 7 pages of appendices. v2 update fixes the arXiv reference in the abstract. v3 update: due to recent work the size of the database was increased adding in the modular data for groups with order 48-63 inclusive. Additionally parts of the paper have been re-written based off referee suggestions

A widely studied model of influence diffusion in social networks represents the network as a graph $G=(V,E)$ with an influence threshold $t(v)$ for each node. Initially the members of an initial set $S\subseteq V$ are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node $v$ that has at least $t(v)$ previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using \emph{incentives} to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks., An extended abstract of this paper was presented at the 25th International Colloquium on Structural Information and Communication Complexity (Sirocco 2018) June 18-21, 2018 Ma'ale HaHamisha, Israel

In the second section "Courant-Gelfand theorem" of his last published paper (Topological properties of eigenoscillations in mathematical physics, Proc. Steklov Institute Math. 273 (2011) 25--34), Arnold recounts Gelfand's strategy to prove that the zeros of any linear combination of the $n$ first eigenfunctions of the Sturm-Liouville problem $$-\, y"(s) + q(x)\, y(x) = \lambda\, y(x) \mbox{ in } ]0,1[\,, \mbox{ with } y(0)=y(1)=0\,,$$divide the interval into at most $n$ connected components, and concludes that "the lack of a published formal text with a rigorous proof \dots is still distressing." Inspired by Quantum mechanics, Gelfand's strategy consists in replacing the ana\-lysis of linear combinations of the $n$ first eigenfunctions by that of their Slater determinant which is the first eigenfunction of the associated $n$-particle operator acting on Fermions. In the present paper, we implement Gelfand's strategy, and give a complete proof of the above assertion. As a matter of fact, refining Gelfand's strategy, we prove a stronger property taking the multiplicity of zeros into account, a result which actually goes back to Sturm (1836)., Comment: Comments: One subsection deleted. References added. Minor corrections

For $x\in End(K^n)$ satisfying $x^2 = 0$ let $F_x$ be the variety of full flags stable under the action of $x$ (Springer fiber over $x$). The full classification of the components of $F_x$ according to their smoothness was provided in a paper of Fresse-Melnikov in terms of both Young tableaux and link patterns. Moreover in a paper of Fresse the purely combinatorial algorithm to compute the singular locus of a singular components of $F_x$ is provided. However this algorithm involves the computation of the graph of the component, and the complexity of computations grows very quickly, so that in practice it is impossible to use it. In this paper, we construct another algorithm, derived from the algorithm of Fresse, providing all the components of the singular locus of a singular component of $F_x$ in terms of link patterns constructed straightforwardly from its link pattern., 34 pages

In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered in the paper, assuming that an optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on $\log R$ to optimize quasiconvex functions in the ball of integer radius $R$ using only the comparison oracle. On the other hand, if an optimized function is conic, then we show that there is a polynomial on $\log R$ algorithm. We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes., Some new proofs have been added. Some fixes are done

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and G\"{o}ring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This improves a previous result for subcubic plane graphs by Andova, Lidick\'y, Lu\v{z}ar, and \v{S}krekovski (2018). We conclude the paper by proposing some problems., Comment: 8 pages, 5 figures

In this paper we consider space-time codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also point out that lattice codes based on Q-central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all Q-central division algebra codes that are based on standard embeddings., Comment: 6 pages, 1 figure. Conference paper submitted to the International Symposium on Information Theory 2018

This paper introduces a new class of Dynkin games, where the two players are allowed to make their stopping decisions at a sequence of exogenous Poisson arrival times. The value function and the associated optimal stopping strategy are characterized by the solution of a backward stochastic differential equation. The paper further provides a replication strategy for the game and applies the model to study the optimal conversion and calling strategies of convertible bonds, and their asymptotics when the Poisson intensity goes to infinity.\ud \ud \ud

We prove a partial converse to the main theorem of the author's previous paper "Proper affine actions: a sufficient criterion" (submitted; available at arXiv:1612.08942). More precisely, let $G$ be a semisimple real Lie group with a representation $\rho$ on a finite-dimensional real vector space $V$, that does not satisfy the criterion from the previous paper. Assuming that $\rho$ is irreducible and under some additional assumptions on $G$ and $\rho$, we then prove that there does not exist a group of affine transformations acting properly discontinuously on $V$ whose linear part is Zariski-dense in $\rho(G)$., Comment: This version differs from the previous one only by a reference that I added

The cycle polynomial of a finite permutation group $G$ is the generating function for the number of elements of $G$ with a given number of cycles: \[F_G(x) = \sum_{g\in G}x^{c(g)},\] where $c(g)$ is the number of cycles of $g$ on $\Omega$. In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of $G$; this is the orbital chromatic polynomial of $\Gamma$ and $G$, where $\Gamma$ is a $G$-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where $\Gamma$ is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group., Comment: 16 pages

The aim of this paper is to study the $w^*$-fixed point property for nonexpansive mappings in the duals of separable Lindenstrauss spaces by means of suitable geometrical properties of the dual ball. First we show that a property concerning the behaviour of a class of $w^*$-closed subsets of the dual sphere is equivalent to the $w^*$-fixed point property. Then, the main result of our paper shows an equivalence between another, stronger geometrical property of the dual ball and the stable $w^*$-fixed point property. The last geometrical notion was introduced by Fonf and Vesel\'{y} as a strengthening of the notion of polyhedrality. In the last section we show that also the first geometrical assumption that we have introduced can be related to a polyhedral concept for the predual space. Indeed, we give a hierarchical structure among various polyhedrality notions in the framework of Lindenstrauss spaces. Finally, as a by-product, we obtain an improvement of an old result about the norm-preserving compact extension of compact operators.

In this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern $2-41-3$, which we call semi-Baxter permutations, and those avoiding the vincular patterns $2-41-3$, $3-14-2$ and $3-41-2$, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding $2-14-3$). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter -- or equivalently, plane -- and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non D-finite., Comment: Version 3 incorporates changes suggested by a referee. Most important changes are that the paths sections have been removed and that the proof of the asymptotic equivalent has been simplified

Every graph $G$ can be represented by a collection of equi-radii spheres in a $d$-dimensional metric $\Delta$ such that there is an edge $uv$ in $G$ if and only if the spheres corresponding to $u$ and $v$ intersect. The smallest integer $d$ such that $G$ can be represented by a collection of spheres (all of the same radius) in $\Delta$ is called the sphericity of $G$, and if the collection of spheres are non-overlapping, then the value $d$ is called the contact-dimension of $G$. In this paper, we study the sphericity and contact dimension of the complete bipartite graph $K_{n,n}$ in various $L^p$-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems., Comment: The paper was previously titled, "The Curse of Medium Dimension for Geometric Problems in Almost Every Norm"