Search

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

We introduce our efforts within the project ‘The science of deep specification’ to work out the key formal underpinnings of industrial-scale formal specifications of software and hardware components, anticipating a world where large verified systems are routinely built out of smaller verified components that are also used by many other projects. We identify an important class of specification that has already been used in a few experiments that connect strong component-correctness theorems across the work of different teams. To help popularize the unique advantages of that style, we dub itdeep specification, and we say that it encompasses specifications that arerich,two-sided,formalandlive(terms that we define in the article). Our core team is developing a proof-of-concept system (based on the Coq proof assistant) whose specification and verification work is divided across largely decoupled subteams at our four institutions, encompassing hardware microarchitecture, compilers, operating systems and applications, along with cross-cutting principles and tools for effective specification. We also aim to catalyse interest in the approach, not just by basic researchers but also by users in industry.This article is part of the themed issue ‘Verified trustworthy software systems’.

International audience; In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms of an expression which allow to define the automaton and the detailed full proof of the property.

Cooperative games form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing some of the most important solution concepts proposed in the literature. For this reason, a relevant question is whether one can give a polynomial-time characterization of submodular instances, for prominent cooperative games that are in general non-convex. In this paper, we focus on a fundamental and widely studied cooperative game, namely the spanning tree game. An efficient recognition of submodular instances of this game was not known so far, and explicitly mentioned as an open question in the literature. We here settle this open problem by giving a polynomial-time characterization of submodular spanning tree games.

We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is no worse than $$O(d^2/\ell ^2)$$ O ( d 2 / ℓ 2 ) in the regime $$\ell = \Omega (d)$$ ℓ = Ω ( d ) where $$\ell $$ ℓ is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Klerk and Laurent (arXiv:1904.08828 ). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the Doherty–Parrilo–Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascués, Owari and Plenio.

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach., arXiv admin note: substantial text overlap with arXiv:1902.05345

Let I be the Stanley–Reisner ideal of a simplicial complex Δ. In this short paper, we shall give a formula of vanishing of the local cohomology modules for S/I(r) in the case Δ is a union of disjoint matroids, where I(r) is the rth symbolic power of I. As an application, we will improve a previous result in Minh and Nakamura (Nagoya Math. J. 213, 127–140, 2014) for the k-Buchsbaumness of S/I(r).

We study the classical \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\varOmega (\sqrt{\log n})}}$$\end{document}2Ω(logn), assuming \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}\not \subseteq \mathsf {DTIME}(n^{\mathcal {O}(\log n)})}$$\end{document}NP⊈DTIME(nO(logn)). This constitutes a significant gap to the best known approximation upper bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al. (Theory Comput 2:137–146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365–374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(1)}$$\end{document}O(1)-approximation when edges (or nodes) may be used by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}\left( \log n/\log \log n\right) }$$\end{document}Ologn/loglogn paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MaxEDP, we give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{r} \log ({k}r))}$$\end{document}O(rlog(kr))-approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al., as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r\le n}$$\end{document}r≤n.Further, we show how to route \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varOmega ({\text {OPT}}^{*})}$$\end{document}Ω(OPT∗) pairs with congestion bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\log (kr)/\log \log (kr))}$$\end{document}O(log(kr)/loglog(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MaxNDP, we give an algorithm that gives the optimal answer in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(k+r)^{\mathcal {O}(r)}\cdot n}$$\end{document}(k+r)O(r)·n. This is a substantial improvement on the run time of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^kr^{\mathcal {O}(r)}\cdot n}$$\end{document}2krO(r)·n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard even for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r=1}$$\end{document}r=1, and MaxNDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {W}[1]}$$\end{document}W[1]-hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {FPT}= \mathsf {W}[1]}$$\end{document}FPT=W[1] and that our approximability results are relevant even for very small constant values of r.

In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set S⊆ { 0 ,1 } n by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula ϕ defining the target set S. The new relaxation is obtained by “feeding” the convex set into the formula ϕ. We analyze various aspects regarding the strength of our procedure. As one application, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems., SCOPUS: ar.j, info:eu-repo/semantics/published

Satisfiability of Boolean circuits is among the most known and important problems in theoretical computer science. This problem is NP-complete in general but becomes polynomial time when restricted either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is strictly connected with the problems of solving equations (or systems of equations) over finite algebras. The research reported in this work was motivated by a desire to know for which finite algebras $\mathbf A$ there is a polynomial time algorithm that decides if an equation over $\mathbf A$ has a solution. We are also looking for polynomial time algorithms that decide if two circuits over a finite algebra compute the same function. Although we have not managed to solve these problems in the most general setting we have obtained such a characterization for a very broad class of algebras from congruence modular varieties. This class includes most known and well-studied algebras such as groups, rings, modules (and their generalizations like quasigroups, loops, near-rings, nonassociative rings, Lie algebras), lattices (and their extensions like Boolean algebras, Heyting algebras or other algebras connected with multi-valued logics including MV-algebras). This paper seems to be the first systematic study of the computational complexity of satisfiability of non-Boolean circuits and solving equations over finite algebras. The characterization results provided by the paper is given in terms of nice structural properties of algebras for which the problems are solvable in polynomial time., 50 pages

Differential-algebraic equations (DAEs) are widely used for modeling of dynamical systems. In numerical analysis of DAEs, consistent initialization and index reduction are important preprocessing prior to numerical integration. Existing DAE solvers commonly adopt structural preprocessing methods based on combinatorial optimization. Unfortunately, the structural methods fail if the DAE has numerical or symbolic cancellations. For such DAEs, methods have been proposed to modify them to other DAEs to which the structural methods are applicable, based on the combinatorial relaxation technique. Existing modification methods, however, work only for a class of DAEs that are linear or close to linear. This paper presents two new modification methods for nonlinear DAEs: the substitution method and the augmentation method. Both methods are based on the combinatorial relaxation approach and are applicable to a large class of nonlinear DAEs. The substitution method symbolically solves equations for some derivatives based on the implicit function theorem and substitutes the solution back into the system. Instead of solving equations, the augmentation method modifies DAEs by appending new variables and equations. The augmentation method has advantages that the equation solving is not needed and the sparsity of DAEs is retained. It is shown in numerical experiments that both methods, especially the augmentation method, successfully modify high-index DAEs that the DAE solver in MATLAB cannot handle., Comment: A preliminary version of this paper is to appear in Proceedings of the 44th International Symposium on Symbolic and Algebraic Computation (ISSAC 2019), Beijing, China, July 2019

This is a follow-up paper of arXiv:1805.00115, where rational curves in surfaces that satisfy general positioned point and cross-ratio conditions were enumerated. A suitable correspondence theorem provided in arXiv:1509.07453 allowed us to use tropical geometry, and, in particular, a degeneration technique called floor diagrams. This correspondence theorem also holds in higher dimension. In the current paper, we introduce so-called cross-ratio floor diagrams and show that they allow us to determine the number of rational space curves that satisfy general positioned point and cross-ratio conditions. Moreover, graphical contributions are introduced which provide a novel and structured way of understanding multiplicities of floor decomposed curves in $\mathbb{R}^3$. Additionally, so-called condition flows on a tropical curve are used to reflect how conditions imposed on a tropical curve yield different types of edges. This concept is applicable in arbitrary dimension., 36 pages, 15 figures; fixed minor issues, added references

Let us fix a prime $p$. The Erd\H{o}s-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero. In this paper, we give a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$. In particular, we prove that any subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero has size at most $C_p\cdot \left(2\sqrt{p}\right)^n$, where $C_p$ is a constant only depending on $p$. For $p$ and $n$ going to infinity, our bound is of the form $p^{(1/2)\cdot (1+o(1))n}$, whereas all previously known upper bounds were of the form $p^{(1-o(1))n}$ (with $p^n$ being a trivial bound). Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method. This method and its consequences were already applied by Naslund as well as by Fox and the author to prove bounds for the problem studied in this paper. However, using some key new ideas, we significantly improve their bounds., Comment: 11 pages

Let $S \subset \Bbb R^n$ be a smooth compact hypersurface with a strictly positive second fundamental form, $E$ be the Fourier extension operator on $S$, and $X$ be a Lebesgue measurable subset of $\Bbb R^n$. If $X$ contains a ball of each radius, then the problem of determining the range of exponents $(p,q)$ for which the estimate $\| Ef \|_{L^q(X)} \leq C \| f \|_{L^p(S)}$ holds is equivalent to the restriction conjecture. In this paper, we study the estimate under the following assumption on the set $X$: there is a number $0 < \alpha \leq n$ such that $|X \cap B_R| \leq c \, R^\alpha$ for all balls $B_R$ in $\Bbb R^n$ of radius $R \geq 1$. On the left-hand side of this estimate, we are integrating the function $|Ef(x)|^q$ against the measure $\chi_X dx$. Our approach consists of replacing the characteristic function $\chi_X$ of $X$ by an appropriate weight function $H$, and studying the resulting estimate in three different regimes: small values of $\alpha$, intermediate values of $\alpha$, and large values of $\alpha$. In the first regime, we establish the estimate by using already available methods. In the second regime, we prove a weighted H\"{o}lder-type inequality that holds for general non-negative Lebesgue measurable functions on $\Bbb R^n$, and combine it with the result from the first regime. In the third regime, we borrow a recent fractal Fourier restriction theorem of Du and Zhang and combine it with the result from the second regime. In the opposite direction, the results of this paper improve on the Du-Zhang theorem in the range $0 < \alpha < n/2$., Comment: 31 pages. Minor revision

A classical theorem of Koksma states that for Lebesgue almost every $x>1$ the sequence $(x^n)_{n=1}^{\infty}$ is uniformly distributed modulo one. In the present paper we extend Koksma's theorem to the pair correlation setting. More precisely, we show that for Lebesgue almost every $x>1$ the pair correlations of the fractional parts of $(x^n)_{n=1}^{\infty}$ are asymptotically Poissonian. The proof is based on a martingale approximation method., Version 2: some minor changes. The paper will appear in the Israel Journal of Mathematics

This is the first of a series of two papers dealing with local limit theorems in relatively hyperbolic groups. In this first paper, we prove rough estimates for the Green function. Along the way, we introduce the notion of relative automaticity which will be useful in both papers and we show that relatively hyperbolic groups are relatively automatic. We also define the notion of spectral positive recurrence for random walks on relatively hyperbolic groups. We then use our estimates for the Green function to prove that $p_n\asymp R^{-n}n^{-3/2}$ for spectrally positive-recurrent random walks, where $p_n$ is the probability of going back to the origin at time n and where R is the inverse of the spectral radius of the random walk.

The Σ-invariants of Bieri–Neumann–Strebel and Bieri–Renz involve an action of a discrete group G on a geometrically suitable space M. In the early versions, M was always a finite-dimensional Euclidean space on which G acted by translations. A substantial literature exists on this, connecting the invariants to group theory and to tropical geometry (which, actually, Σ-theory anticipated). More recently, we have generalized these invariants to the case where M is a proper CAT(0) space on which G acts by isometries. The “zeroth stage” of this was developed in our paper [BG16]. The present paper provides a higher-dimensional extension of the theory to the “nth stage” for any n.

In this paper we study 1/k geodesics, those closed geodesics that minimize on all subintervals of length $L/k$, where $L$ is the length of the geodesic. We develop new techniques to study the minimizing properties of these curves on doubled polygons, and demonstrate a sequence of doubled polygons whose closed geodesics exhibit unbounded minimizing properties. We also compute the length of the shortest closed geodesic on doubled odd-gons and show that this length approaches 4 times the diameter., Comment: This paper is a result of a SUMRY (REU) project at Yale

In 1936 W. Burau discovered an interesting family of n×n matrices that give a linear representation of Artin’s classical braid group Bn, n=1,2,…. A natural question followed very quickly: is the so-called Burau representation faithful? Over the years it was proved to be faithful for n≤3, nonfaithful for n≥5, but the case of n=4 remains open to this day, in spite of many papers on the topic. This paper introduces braid groups, describes the problem in ways that make it accessible to readers with a minimal background, reviews the literature, and makes a contribution that reinforces conjectures that the Burau representation of B4 is faithful.

This paper is devoted to the stochastic properties of dynamical systems preserving an infinite measure. More precisely we prove central limit theorems for Birkhoff sums of observables of ℤ2-extensions of dynamical systems (satisfying some nice spectral properties). The motivation of our paper is the ℤ2-periodic Lorentz process for which we establish a functional central limit theorem for Holder continuous observables (in discrete time as well as in continuous time).

In this paper we study some cube packing problems. In particular we are interested in compact subsets of $\mathbb{R}^n,n\geq 2$, which contain boundaries of cubes with all side lengths in $(0,1)$. We show here that such sets must have lower box dimension at least $n-0.5$ and we will also provide sharp examples. We also show here that such sets must be large in general in a precise sense which is also introduced in this paper., 9 pages. arXiv admin note: text overlap with arXiv:1711.06533

In this paper we study a connective commutative differential graded algebra (CDGA) which is piecewise Noetherian. The principal aim is to analyze a dualizing complex of CDGA’s and investigate a Gorenstein CDGA. We also establish many other results which can be expected to play basic roles in the study of a CDGA, such as the Auslaner-Buchsbaum formula and Bass formula without any unnecessary assumptions. The key notion is the sup-projective (sppj) and inf-injective (ifij) resolutions introduced by the author, which are DG-versions of the projective and injective resolutions for ordinary modules. In the paper, we show that sppj and ifij resolutions are powerful tools to study DG-modules.

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model $G(2n,p,q)$, which is a random graph consisting of two distinct Erdős-Renyi graphs $G(n,p)$ joined by random edges with density $q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and $r=q/p$ is a constant, we show that there is a phase transition in $r$ with threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and $r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion configuration with a bias of $\Omega(n)$. By contrast, if $r r^*$, we show that, for any initial opinion configuration, the process reaches consensus within $O(\log n)$ steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

In their remarkable paper, Minakshisundaram and Pleijel established by using the parametrix for the heat equation the asymptotic expansion of the heat kernel on compact Riemannian manifolds. The result has since been extensively used in the spectral analysis of the Laplace-Beltrami operator, and in particular, in proving Weyl’s law for the asymptotic distribution of eigenvalues and various direct and inverse problems in spectral geometry. However, the question of describing the explicit values of the corresponding heat trace coefficients associated with an arbitrary compact Riemannian manifold has remained an interesting task. In this paper, we review results on Minakshisundaram-Pleijel coefficients associated with the Laplacian on spheres $${\mathbb {S}}^{N}$$ ( $$N\ge 1$$ ) and other associated spectral invariants, namely, the Minakshisundaram-Pleijel zeta functions & their residues, and the zeta-regularised determinants of the Laplacian on spheres. The results reviewed deal mainly with closed-form formulae for the afore-mentioned spectral invariants and the explicit values of the first few of these spectral invariants are given.

In this paper, we revisit the performance of theα-synchronizer in distributed systems with probabilistic message loss as introduced in Függer et al. [Perf. Eval. 93(2015)]. In sharp contrast to the infinite-state Markov chain resp. the exponential-size finite-state upper bound presented in the original paper, we introduce a polynomial-size finite-state Markov chain for a new synchronizer variant$\alpha ^{\prime }$α′, which provides a new upper bound on the performance of theα-synchronizer. Both analytic and simulation results show that our new upper bound is strictly better than the existing one. Moreover, we show that a modified version of the$\alpha ^{\prime }$α′-synchronizer provides a lower bound on the performance of theα-synchronizer. By means of elaborate simulation results, we show that our new lower bound is also strictly better than the lower bound presented in the original paper.

In this paper, we show how to use the framework of mod-Gaussian convergence in order to study the fluctuations of certain models of random graphs, of random permutations and of random integer partitions. We prove that, in these three frameworks, a generic homogeneous observable of a generic random model is mod-Gaussian under an appropriate renormalisation. This implies a central limit theorem with an extended zone of normality, a moderate deviation principle, an estimate of the speed of convergence, a local limit theorem and a concentration inequality. The universal asymptotic behavior of the observables of these models gives rise to a notion of mod-Gaussian moduli space., Comment: New version: the paper has been slightly shortened, and a few references were added. 52 pages, 13 figures

A graph Γ is called a bi-circulant if it admits a cyclic group as a group of automorphisms acting semiregularly on the vertices of Γ with two orbits. The characterization of tetravalent edgetransitive bi-circulants was given in several recent papers. In this paper, a classification is given of connected tetravalent vertex-transitive bi-circulants of order twice an odd integer.

The authors developed in a recent paper natural dualities for finitely generated quasivarieties of Sugihara algebras. They thereby identified the admissibility algebras for these quasivarieties which, via the Test Spaces Method devised by Cabrer et al., give access to a viable method for studying admissible rules within relevance logic, specifically for extensions of the deductive system R-mingle.This paper builds on the work already done on the theory of natural dualities for Sugihara algebras. Its purpose is to provide an integrated suite of multisorted duality theorems of a uniform type, encompassing finitely generated quasivarieties and varieties of both Sugihara algebras and Sugihara monoids, and embracing both the odd and the even cases. The overarching theoretical framework of multisorted duality theory developed here leads on to amenable representations of free algebras. More widely, it provides a springboard to further applications.

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or "small enough") finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and S\'enizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions., Comment: 72 pages, 14 figures. Small edits to the exposition in Section 15. An extended abstract of a preliminary version of this paper was presented at ICALP 2017

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work., Comment: An an earlier version of this paper appeared in SODA 2010. That paper contained preliminary versions of some of the results of this paper

In this paper, we develop the elementary theory of inverse semigroups to the cases of type B semigroups. The main aim of this paper is to study proper type B semigroups. We introduce first the concept of a left admissible triple. After obtaining some basic properties of left admissible triple, we give the definition of a Q-semigroup and get a structure theorem of Q-semigroup. In particular, we introduce the notion of an admissible triple and give some characterization of proper type B semigroups. It is proved that an arbitrary Q-semigroup with an admissible triple is an E-unitary type B semigroup.

Let G be a graph with vertex set V(G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …, |E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to $${{1 + \left| {E(G)} \right|} \over 2} \cdot d(v)$$ , where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V(G), |{e : e ∈ Ev, f(e) ≤ Δ/2}| = |{e : e ∈ Ev, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.

Associated to a presentable $\infty$-category $\mathcal{C}$ and an object $X \in \mathcal{C}$ is the tangent $\infty$-category $\mathcal{T}_X\mathcal{C}$, consisting of parameterized spectrum objects over $X$. This gives rise to a cohomology theory, called Quillen cohomology, whose category of coefficients is $\mathcal{T}_X\mathcal{C}$. When $\mathcal{C}$ consists of algebras over a nice $\infty$-operad in a stable $\infty$-category, $\mathcal{T}_X\mathcal{C}$ is equivalent to the $\infty$-category of operadic modules, by work of Basterra--Mandell, Schwede and Lurie. In this paper we develop the model-categorical counterpart of this identification and extend it to the case of algebras over an enriched operad, taking values in a model category which is not necessarily stable. This extended comparison can be used, for example, to identify the cotangent complex of enriched categories, an application we take up in a subsequent paper., Comment: The section concerning stabilization of model categories was separated into an independent paper, appearing now as arXiv:1802.08031

In the first part of the paper, we clarify the connections between several algebraic objects appearing in matroid theory: both partial fields and hyperfields are fuzzy rings, fuzzy rings are tracts, and these relations are compatible with the respective matroid theories. Moreover, fuzzy rings are ordered blueprints and lie in the intersection of tracts with ordered blueprints; we call the objects of this intersection pastures. In the second part, we construct moduli spaces for matroids over pastures. We show that, for any non-empty finite set $E$, the functor taking a pasture $F$ to the set of isomorphism classes of rank-$r$ $F$-matroids on $E$ is representable by an ordered blue scheme $Mat(r,E)$, the moduli space of rank-$r$ matroids on $E$. In the third part, we draw conclusions on matroid theory. A classical rank-$r$ matroid $M$ on $E$ corresponds to a $\mathbb{K}$-valued point of $Mat(r,E)$ where $\mathbb{K}$ is the Krasner hyperfield. Such a point defines a residue pasture $k_M$, which we call the universal pasture of $M$. We show that for every pasture $F$, morphisms $k_M\to F$ are canonically in bijection with $F$-matroid structures on $M$. An analogous weak universal pasture $k_M^w$ classifies weak $F$-matroid structures on $M$. The unit group of $k_M^w$ can be canonically identified with the Tutte group of $M$. We call the sub-pasture $k_M^f$ of $k_M^w$ generated by ``cross-ratios' the foundation of $M$,. It parametrizes rescaling classes of weak $F$-matroid structures on $M$, and its unit group is coincides with the inner Tutte group of $M$. We show that a matroid $M$ is regular if and only if its foundation is the regular partial field, and a non-regular matroid $M$ is binary if and only if its foundation is the field with two elements. This yields a new proof of the fact that a matroid is regular if and only if it is both binary and orientable., 85 pages; some additional material, e.g. a new section 5.6; the terminology has been adapted to the usage in follow-up papers

This paper discusses and provides some analytical studies for a modified fractional-order SIRD mathematical model of the COVID-19 epidemic in the sense of the Caputo–Katugampola fractional derivative that allows treating of the biological models of infectious diseases and unifies the Hadamard and Caputo fractional derivatives into a single form. By considering the vaccine parameter of the suspected population, we compute and derive several stability results based on some symmetrical parameters that satisfy some conditions that prevent the pandemic. The paper also investigates the problem of the existence and uniqueness of solutions for the modified SIRD model. It does so by applying the properties of Schauder’s and Banach’s fixed point theorems.

This paper is devoted to the study of the quadruple Roman domination in trees, and it is a contribution to the Special Issue “Theoretical computer science and discrete mathematics” of Symmetry. For any positive integer k, a [k]-Roman dominating function ([k]-RDF) of a simple graph G is a function from the vertex set V of G to the set {0,1,2,…,k+1} if for any vertex u∈V with f(u)&lt, k, ∑x∈N(u)∪{u}f(x)≥|{x∈N(u):f(x)≥1}|+k, where N(u) is the open neighborhood of u. The weight of a [k]-RDF is the value Σv∈Vf(v). The minimum weight of a [k]-RDF is called the [k]-Roman domination number γ[kR](G) of G. In this paper, we establish sharp upper and lower bounds on γ[4R](T) for nontrivial trees T and characterize extremal trees.

The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of d-cycles, d-hypertrees and d-hypercuts are, respectively, (d +1)-, d-and (n − d − 1)-vertex-connected. It is also shown that the facet graph of a d-cycle cannot be split into more than s connected components by removing at most s vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.

We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. In a recent paper [Simon et al. 2011], the authors used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of Kullback-Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed., Comment: 28 pages, 4 figures

A uniform attachment graph (with parameter $k$), denoted $G_{n,k}$ in the paper, is a random graph on the vertex set $[n]$, where each vertex $v$ makes $k$ selections from $[v-1]$ uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well-studied random graphs: $k$-out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of $G_{n,k}$ to show that the conductance of $G_{n,k}$ is of order $(\log n)^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where, each vertex is either initially infected with probability $p$, independently of others, or gets infected later as a result of having $r$ infected neighbors at some point. We show that, for $2\le r\le k-1$, if $p\ll (\log n)^{-r/(r-1)}$, then, with probability approaching 1, the process ends before all vertices get infected. On the other hand, if $p\ge \omega(\log n)^{-r/(r-1)}$, where $\omega$ is a certain very slowly growing function, then all the vertices get infected with probability approaching 1.

Let P be a Borel probability measure on ℝ generated by an infinite system of similarity mappings {Sj : j ∈ ℕ} such that $$P=\Sigma_{j=1}^{\infty}\frac{1}{2^{j}}P\circ{S}_j^{-1}$$ , where for each j ∈ ℕ and x ∈ ℝ, $$S_j(x)=\frac{1}{3^j}x+1-\frac{1}{3^{j-1}}$$ . Then, the support of P is the dyadic Cantor set C generated by the similarity mappings f1, f2 : ℝ → ℝ such that f1(x) = 1/3x and f2(x) = 1/3x+ 2/3 for all x ∈ ℝ. In this paper, using the infinite system of similarity mappings {Sj : j ∈ ℕ} associated with the probability vector $$(\frac{1}{2},\frac{1}{{{2^2}}},...)$$ , for all n ∈ ℕ, we determine the optimal sets of n-means and the nth quantization errors for the infinite self-similar measure P. The technique obtained in this paper can be utilized to determine the optimal sets of n-means and the nth quantization errors for more general infinite self-similar measures.

In [BGLM] and [GLNP] it was conjectured that if $H$ is a simple Lie group of real rank at least 2, then the number of conjugacy classes of (arithmetic) lattices in $H$ of covolume at most $x$ is $x^{(\gamma(H)+o(1))\log x/\log\log x}$ where $\gamma(H)$ is an explicit constant computable from the (absolute) root system of $H$. In [BLu] we disproved this conjecture. In this paper we prove that for most groups $H$ the conjecture is actually true if we restrict to counting only non-uniform lattices., Comment: 23 pages, revised following referee's comments. Dedicated to Aner Shalev on his 60th birthday. This paper is related to our previous work arXiv:0905.1841 with which it shares some preliminaries

In this paper we determine the largest sets of points of finite thick buildings of type F4 such that no two points of the set are at maximal distance. The motivation for studying these sets comes from [9], where a general Erdős–Ko–Rado problem was formulated for finite thick buildings. The result in this paper solves this problem for points (and dually for symplecta) in finite thick buildings of type F4.

Recent studies of [Formula: see text]-groups of coclass [Formula: see text] concentrate on the coclass graph [Formula: see text]. While the detailed structure of [Formula: see text] is unknown, it is known that its general structure is dominated by the subgraph of ‘skeleton groups’. The original definition of these groups is technical, but some modifications for special cases have been used successfully in the literature. Given their importance, in this paper we define and investigate skeleton groups more rigorously. In particular, we study their isomorphism problem, which is a crucial step towards understanding the skeleton subgraph of [Formula: see text]. During our work we identified erroneous arguments for constructing isomorphisms in a proof of the 2013 paper on [Formula: see text]. We correct these errors here by proving the required results in a more general context.

In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model arises from the positive part of an algebraic variety determined by the slack ideal of the polytope. This is a saturated determinantal ideal that encodes the combinatorics of the polytope. We also derive a new model of the realization space of a polytope from the positive part of the variety of a related ideal. The slack ideal offers an effective computational framework for several classical questions about polytopes such as rational realizability, non-prescribability of faces, and realizability of combinatorial polytopes., Comment: The original arXiv submission of this paper has now been split into two parts; this paper describing the slack realization space of a polytope and applications of the slack ideal, and a second paper focussing on toric slack ideals and projective uniqueness

Kavut, Selçuk (Balikesir Author), Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [IEEE Trans. Inform. Theory, 64 ( 2018), pp. 393-402] by modifying the PSap class of bent functions. The basic ideas used in Tang-Maitra construction were derived from a modification of a subclass of bent functions which is defined over the finite field, and a concern was raised in the same paper whether the implementation of such functions will be as efficient as that of Maiorana-McFarland type bent functions. In this paper, we look at the concrete realization of such functions over a vector space and answer the question positively. The first part of this paper investigates how the finite field implementation of the functions can be viewed as simple truth tables. Next, we present a completely new construction that itself starts from Maiorana-McFarland bent functions which are straightforward concatenations of linear functions., National Natural Science Foundation of China - 61872435 61602394 Fundamental Research Funds for the Central Universities - 2682016CX113 2682018ZT25

Two permutations of $[n]=\{1,2 \ldots n\}$ are \textit{$k$-neighbor separated} if there are two elements that are neighbors in one of the permutations and that are separated by exactly $k-2$ other elements in the other permutation. Let the maximal number of pairwise $k$-neighbor separated permutations of $[n]$ be denoted by $P(n,k)$. In a previous paper, the authors have determined $P(n,3)$ for every $n$, answering a question of K\"orner, Messuti and Simonyi affirmatively. In this paper we prove that for every fixed positive integer $\ell $, $$P(n,2^\ell+1) = 2^{n-o(n)}. $$ We conjecture that for every fixed even $k$, $P(n,k)=2^{n-o(n)}$. We also show that this conjecture is asymptotically true in the following sense $$\lim_{k \rightarrow \infty} \lim_{n \rightarrow \infty} \sqrt[n]{P(n,k)}=2.$$ Finally, we show that for even $n$, $P(n,n)= 3n/2$.

A $(\beta,\epsilon)$-hopset for a weighted undirected $n$-vertex graph $G=(V,E)$ is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most $\beta$ edges, whose length is within $1+\epsilon$ of the shortest path. In her seminal paper, Cohen \cite[JACM 2000]{C00} introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various other settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen \cite{C00} devised efficient algorithms for constructing hopsets with {\em polylogarithmic} in $n$ number of hops. Her constructions remain the state-of-the--art since the publication of her paper in STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a {\em constant number of hops}. We also find efficient algorithms for hopsets in various computational settings, improving the best known constructions. Generally, our hopsets strictly outperform the hopsets of \cite{C00}, both in terms of their parameters, and in terms of the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from $s$ sources. Our results improve the running time for this problem in the parallel, distributed and streaming models, for a vast range of $s$.

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a $(1-g(\varepsilon))$-fraction of constraints on any $(1-\varepsilon)$-satisfiable instance, where the loss function $g$ is such that $g(\varepsilon)\rightarrow 0$ as $\varepsilon\rightarrow 0$. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some $g$) have been characterised by Barto and Kozik, with the general bound on the loss $g$ being doubly exponential, specifically $g(\varepsilon)=O((\log\log(1/\varepsilon))/\log(1/\varepsilon))$. It is natural to ask when a better loss can be achieved: in particular, polynomial loss $g(\varepsilon)=O(\varepsilon^{1/k})$ for some constant $k$. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter $k$ in the loss depends on the size of the domain and the arity of the relations in $\Gamma$, while the other works for a special ternary near-unanimity operation called dual discriminator with $k=2$ for any domain size. In the latter case, the CSP is a common generalisation of Unique Games with a fixed domain and 2-SAT. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for CSP., Comment: A preliminary version of this paper appeared in SODA 2017. Journal referees' comments are incorporated

This paper is the first one in a series of papers where we lay special attention on syntax and semantics in knowledge base theory. The main goal of the present paper is to set up all necessary mathematical background for the definition of a knowledge-base model which will be introduced in the next paper. We should emphasize that in these papers we develop a slightly different approach to the knowledge-base model than in the previous ones.