Search

A subset $D \subseteq V$ is an \emph{independent} (or \emph{stable}) \emph{dominating set} of a graph $G = (V,E)$ if $D$ is an independent set (no edges between vertices of $D$) and dominates all the vertices of $G$ (each vertex of $V-D$ has a neighbour in $D$). In this paper we study a generalisation of this classical notion. Namely, an instance of our problem is a graph $G=(V, E)$ and $\Pi=(V_1, \dots, V_k)$ a partition of $V$. Each subset $V_i$ of $\Pi$ is called an \emph{obligation}. An \emph{Independent Dominating set with Obligation} (\IDO) $D$ in an instance $(G, \Pi)$ is an independent dominating set of $G$ with the additional property that if a vertex $u$ of obligation $V_i$ is in $D$, then \emph{all} the others vertices of $V_i$ must also be in $D$; i.e., for all $i=1,\dots,k$, either $V_i\cap D=\emptyset$ or $V_i \subseteq D$ (we say that $D$ \emph{respects} the obligations). Note that when each obligation of $\Pi$ is a singleton, an \IDO is just an independent dominating set of $G$ that can be constructed with a greedy algorithm. Among other things, we show that determining if an instance $(G=(V,E),\Pi)$ has an \IDO is $NP$-complete, even if $G$ is a path (each vertex of $G$ exactly has two neighbours, except two extremities that have one), all the obligations are independent sets of $G$ and they all have the same constant size $\lambda > 1$. We also show that the problem is also $NP$-complete, even if $\Pi$ is composed of $\sqrt{|V|}$ independent obligations each of size $\sqrt{|V|}$ or if the diameter of $G$ is three. Our results clearly show that this problem is very difficult, even in extremely restricted instances. Hence, in a second part of the paper, we relax the condition to dominate all the vertices of $G$. However, we show that determining if $(G=(V, E), \Pi)$ contains an independent set $D$ respecting the obligations and dominating at least $3\sqrt{|V|} -2$ vertices of $G$ is $NP$-complete, even if $G$ is a collection of disjoint paths and obligations are all independent sets of $G$. On the positive side, we propose a greedy algorithm constructing a solution dominating at least $2\sqrt{|V|} - 1$ vertices in any instance $(G=(V, E), \Pi)$ if all obligations of $\Pi$ are independent sets of $G$.

In this paper, we start the investigation of a new natural approach to "unifying" noncommutative gauge field theories (NCGFT) based on approximately finite-dimensional ($AF$) $C^*$-algebras. The defining inductive sequence of an $AF$ $C^*$-algebra is lifted to enable the construction of a sequence of NCGFT of Yang-Mills-Higgs types. The present paper focus on derivation-based noncommutative field theories. A mathematical study of the ingredients involved in the construction of a NCGFT is given in the framework of $AF$ $C^*$-algebras: derivation-based differential calculus, modules, connections, metrics and Hodge $\star$-operators, Lagrangians... Some physical applications concerning mass spectra generated by Spontaneous Symmetry Breaking Mechanisms (SSBM) are proposed using numerical computations for specific situations., Comment: 42 pages, 20 figures

Paper on stochastic invariance; International audience; In this paper a constructive method to determine and compute probabilistic reachable and invariant sets for linear discrete-time systems, excited by a stochastic disturbance, is presented. The samples of the disturbance signal are not assumed to be uncorrelated, only bounds on the mean and the covariance matrices are supposed to be known. This allows to consider nonlinear stochastic systems approximations and the effect of nonlinear filters on the disturbance. The correlation bound concept is introduced and employed to determine probabilistic reachable sets and probabilistic invariant sets. Constructive methods for their computation, based on convex optimization, are given.

In this paper we consider kinetically constrained models (KCM) on $\mathbb Z^2$ with general update families $\mathcal U$. For $\mathcal U$ belonging to the so-called "critical class" our focus is on the divergence of the infection time of the origin for the equilibrium process as the density of the facilitating sites vanishes. In a recent paper Mar\^ech\'e and two of the present authors proved that if $\mathcal U$ has an infinite number of "stable directions", then on a doubly logarithmic scale the above divergence is twice the one in the corresponding $\mathcal U$-bootstrap percolation. Here we prove instead that, contrary to previous conjectures, in the complementary case the two divergences are the same. In particular, we establish the full universality partition for critical $\mathcal U$. The main novel contribution is the identification of the leading mechanism governing the motion of infected critical droplets. It consists of a peculiar hierarchical combination of mesoscopic East-like motions., Comment: 36 pages, 11 figures, expanded and revised presentation, added roadmaps for sections 4 and 5, added and improved figures

Many systems in life sciences have been modeled by reaction–diffusion equations. However, under some circumstances, these biological systems may experience instantaneous and periodic perturbations (e.g. harvest, birth, release, fire events, etc) such that an appropriate formalism like impulsive reaction–diffusion equations is necessary to analyze them. While several works tackled the issue of traveling waves for monotone reaction–diffusion equations and the computation of spreading speeds, very little has been done in the case of monotone impulsive reaction–diffusion equations. Based on vector-valued recursion equations theory, we aim to present in this paper results that address two main issues of monotone impulsive reaction–diffusion equations. Our first result deals with the existence of traveling waves for monotone systems of impulsive reaction–diffusion equations. Our second result tackles the computation of spreading speeds for monotone systems of impulsive reaction–diffusion equations. We apply our methodology to a planar system of impulsive reaction–diffusion equations that models tree–grass interactions in fire-prone savannas. Numerical simulations, including numerical approximations of spreading speeds, are finally provided in order to illustrate our theoretical results and support the discussion.

International audience; Zero-inflated models have become a popular tool for assessing the relationships between explanatory variables and a zero-inflated count outcome. In these models, regression coefficients have latent class interpretations, where the latent classes correspond to a susceptible subpopulation with observations generated from a count distribution and a non-susceptible subpopulation that provides only zero counts. However, it is often of interest to evaluate covariates effects in the overall mixture population, that is, on the marginal mean of the zero-inflated count response. Marginal zero-inflated models, such as the marginal zero-inflated Poisson and negative binomial models, have been developed for that purpose. They specify independent submodels for the susceptibility probability and the marginal mean of the count response. When the count outcome is bounded, it is tempting to formulate a marginal zero-inflated binomial model in the same fashion. This, however, is not possible, due to the inherent constraints that relate, in the zero-inflated binomial model, the susceptibility probability and the latent and marginal means of the count outcome. In this paper, we propose a marginal zero-inflated binomial regression model that accommodates these constraints. We construct maximum likelihood estimates of the regression parameters. Their asymptotic properties are established and their finite-sample behaviour is examined by simulations. An application of the proposed model to the analysis of health-care demand is provided for illustration.

Although it is well known that the performance of attribute control charts decreases significantly when the assumption of known process parameters is invalid, this assumption is prevalent in the pertinent literature. However, in most practical applications, the process parameters have to be estimated from a finite in-control Phase I sample, and therefore the performance of attribute control charts should be evaluated from the perspective of estimated process parameters. In this paper, we compare the run length properties of the hypergeometric n p chart in both the known and estimated parameter cases. In particular, we investigate the required number of Phase I samples and new specific chart parameters that allow the hypergeometric n p chart with estimated parameter p to have approximately the same in-control performance as in the known parameters case. Moreover, we perform a comprehensive in-control and out-of-control comparison of the hypergeometric n p chart with its binomial counterpart. In order to achieve these objectives, we also present a new approach to effectively compute the probability distribution of the sum of independent and identically hypergeometric-distributed random variables. The proposed approximation reduces the computational effort to a few seconds while keeping a remarkable high accuracy with only negligible deviations compared to the exact distribution obtained via convolution.

International audience; This paper contains two results concerning the spectral decomposition, in a broad sense, of the space of nondegenerate Hermitian matrices over a local field of characteristic zero. The first is an explicit Plancherel decomposition of the associated $L^2$ space thus confirming a conjecture of Sakellaridis-Venkatesh in this particular case. The second is a formula for the multiplicities of generic representations in the $p$-adic case that extends previous work of Feigon-Lapid-Offen. Both results are stated in terms of Arthur-Clozel's quadratic local base-change and the proofs are based on local analogs of two relative trace formulas previously studied by Jacquet and Ye and known as (relative) Kuznetsov trace formulas.

International audience; We present some sharper finite extinction time results for solutions of a class of damped nonlinear Schrödinger equations when the nonlinear damping term corresponds to the limit cases of some ``saturating non-Kerr law'' $F(|u|^2)u=\frac{a}{\varepsilon+(|u|^2)^\alpha}u,$ with $a\in\mathbb{C},$ $\varepsilon\geqslant0,$ $2\alpha=(1-m)$ and $m\in[0,1).$ To carry out the improvement of previous results in the literature we present in this paper a careful revision of the existence and regularity of weak solutions under very general assumptions on the data. We prove that the problem can be solved in the very general framework of the maximal monotone operators theory, even under a lack of regularity of the damping term. This allows us to consider, among other things, the singular case $m=0.$ We replace the above approximation of the damping term by a different one which keeps the monotonicity for any $\varepsilon\geqslant0$. We prove that, when $m=0,$ the finite extinction time of the solution arises for merely bounded right hand side data $f(t,x).$ This is specially useful in the applications in which the Schrödinger equation is coupled with some other functions satisfying some additional equations.

In this paper, we study the sparsity-adapted complex moment-Hermitian sum of squares (moment-HSOS) hierarchy for complex polynomial optimization problems, where the sparsity includes correlative sparsity and term sparsity. We compare the strengths of the sparsity-adapted complex moment-HSOS hierarchy with the sparsity-adapted real moment-SOS hierarchy on either randomly generated complex polynomial optimization problems or the AC optimal power flow problem. The results of numerical experiments show that the sparsity-adapted complex moment-HSOS hierarchy provides a trade-off between the computational cost and the quality of obtained bounds for large-scale complex polynomial optimization problems., 20 pages, 6 tables

International audience; In general, the braid structures in a topological space can be classified into algebraic forms and geometric forms. This paper investigates the properties of a braid structure involving 2-simplices and a set of directed braid-paths in view of algebraic as well as geometric topology. The 2-simplices are of the cyclically oriented variety embedded within the disjoint topological covering subspaces where the finite braid-paths are twisted as well as directed. It is shown that the generated homotopic simplicial braids form Abelian groups and the twisted braid-paths successfully admit several varieties of twisted discrete path-homotopy equivalence classes, establishing a set of simplicial fibers. Furthermore, a set of discrete-loop fundamental groups are generated in the covering spaces where the appropriate weight assignments generate multiplicative group structures under a variety of homological formal sums. Interestingly, the resulting smallest non-trivial group is not necessarily unique. The proposed variety of homological formal sum exhibits a loop absorption property if the homotopy path-products are non-commutative. It is considered that the topological covering subspaces are simply connected under embeddings with local homeomorphism maintaining generality.

In this paper, we study several definitions of generalized rank weights for arbitrary finite extensions of fields. We prove that all these definitions coincide, generalizing known results for extensions of finite fields., Comment: Comments welcome!

We look for solutions to the Schr\"{o}dinger-Poisson-Slater equation $$- \Delta u + \lambda u - \gamma (|x|^{-1} * |u|^2) u - a |u|^{p-2}u = 0 \quad \text{in} \quad \mathbb{R}^3, $$ which satisfy \begin{equation*} \int_{\mathbb{R}^3}|u|^2 \, dx = c \end{equation*} for some prescribed $c>0$. Here $ u \in H^1(\mathbb{R}^3)$, $\gamma \in \mathbb{R},$ $ a \in \mathbb{R}$ and $p \in (\frac{10}{3}, 6]$. When $\gamma >0$ and $a > 0$, both in the Sobolev subcritical case $p \in (\frac{10}{3}, 6)$ and in the Sobolev critical case $p=6$, we show that there exists a $c_1>0$ such that, for any $c \in (0,c_1)$, the equation admits two solutions $u_c^+$ and $u_c^-$ which can be characterized respectively as a local minima and as a mountain pass critical point of the associated {\it Energy} functional restricted to the norm constraint. In the case $\gamma >0$ and $a < 0$, we show that, for any $p \in (\frac{10}{3},6]$ and any $c>0$, the equation admits a solution which is a global minimizer. Finally, in the case $\gamma 0$ and $p=6$ we show that it does not admit positive solutions., Comment: This version is the final one, corresponding to the paper now published in Journal of Differential Equations

Let k be a field of characteristic zero. This paper studies a problem proposed by Joseph F. Ritt in 1950. Precisely, we prove that (1) If p ⩾ 2 is an integer, for every integer i ∈ N , the nilpotency index of the image of T i in the ring k { T } / [ T p ] equals ( i + 1 ) p − i . (2) For every pair of integers ( i , j ) , the nilpotency index of the image of T i U j in the ring k { T } / [ T U ] equals i + j + 1 .

Given n rational inner functions Φ = ( Φ 1 , . . . , Φ n ) defining a 0-dimensional (hence finite) complete intersection in the polydisk D n and a Weil polyhedron Δ r Φ relatively compact in D n , we combine together the Cauchy-Weil representation formulas respectively in D n (considered as a Weil polyhedron subordinated to the coordinate functions) and Δ r Φ in order to provide integral representations formulas involving a positive kernel provided Φ satisfies some Schur-Agler type conditions. We then study interpolation problems in H 2 ( D n ) along the finite set Φ − 1 ( { 0 _ } ) . One of the main objectives of this paper is to emphasize the important role played here by Cauchy-Weil representation formula (as in computational polynomial geometry), together with its intimate connection with multivariate residue calculus.

International audience; This paper develops a method for obtaining guaranteed outer approximations for global attractors of continuous and discrete time nonlinear dynamical systems. The method is based on a hierarchy of semidefinite programming problems of increasing size with guaranteed convergence to the global attractor. The approach taken follows an established line of reasoning, where we first characterize the global attractor via an infinite dimensional linear programming problem (LP) in the space of Borel measures. The dual to this LP is in the space of continuous functions and its feasible solutions provide guaranteed outer approximations to the global attractor. For systems with polynomial dynamics, a hierarchy of finite-dimensional sum-of-squares tightenings of the dual LP provides a sequence of outer approximations to the global attractor with guaranteed convergence in the sense of volume discrepancy tending to zero. The method is very simple to use and based purely on convex optimization. Numerical examples with the code available online demonstrate the method.

International audience; In this paper, we propose, implement and analyze an Authenticated Encryption with Associated Data Scheme (AEADS) based on the Modified Duplex Construction (MDC) that contains a chaotic compression function (CCF) based on our chaotic neural network revised (CNNR). Unlike the standard duplex construction (SDC), in the MDC there are two phases: the initialization phase and the duplexing phase, each contain a CNNR formed by a neural network with single layer, and followed by a set of non-linear functions. The MDC is implemented with two variants of width, i.e., 512 and 1024 bits. We tested our proposed scheme against the different cryptanalytic attacks. In fact, we evaluated the key and the message sensitivity, the collision resistance analysis and the diffusion effect. Additionally, we tested our proposed AEADS using the different statistical tests such as NIST, Histogram, chi-square, entropy, and correlation analysis. The experimental results obtained on the security performance of the proposed AEADS system are notable and the proposed system can then be used to protect data and authenticate their sources.

There have been several existence results for the standing waves of FitzHugh-Nagumo equations. Such waves are the connecting orbits of an autonomous second-order Lagrangian system and the corresponding kinetic energy is an indefinite quadratic form in the velocity terms. When the system has two stable hyperbolic equilibria, there exist two stable standing fronts, which will be used in this paper as building blocks, to construct stable standing waves with multiple fronts in case the equilibria are of saddle-focus type. The idea to prove existence is somewhat close in spirit to [Buffoni-Sere, CPAM 49, 285-305]. However several differences are required in the argument: facing a strongly indefinite functional, we need to perform a nonlo-cal Lyapunov-Schmidt reduction; in order to justify the stability of multiple front standing waves, we rely on a more precise variational characterization of such critical points. Based on this approach, both stable and unstable standing waves are established., Final version to appear in Journal of Differential Equations

Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining even computational completeness with only one catalyst. Last year we could show that the derivation mode $$max_{objects}$$ m a x objects , where we only take those multisets of rules which affect the maximal number of objects in the underlying configuration one catalyst is sufficient for obtaining computational completeness without any other ingredients. In this paper we follow this way of research and show that one catalyst is also sufficient for obtaining computational completeness when using specific variants of derivation modes based on non-extendable multisets of rules: we only take those non-extendable multisets whose application yields the maximal number of generated objects or else those non-extendable multisets whose application yields the maximal difference in the number of objects between the newly generated configuration and the current configuration. A similar computational completeness result can even be obtained when omitting the condition of non-extendability of the applied multisets when taking the maximal difference of objects or the maximal number of generated objects. Moreover, we reconsider simple P system with energy control—both symbol and rule energy-controlled P systems equipped with these new variants of derivation modes yield computational completeness.

International audience; Classification and regression trees (CART) prove to be a true alternative to full parametric models such as linear models (LM) and generalized linear models (GLM). Although CART suffer from a biased variable selection issue, they are commonly applied to various topics and used for tree ensembles and random forests because of their simplicity and computation speed. Conditional inference trees and model-based trees algorithms for which variable selection is tackled via fluctuation tests are known to give more accurate and interpretable results than CART, but yield longer computation times. Using a closed-form maximum likelihood estimator for GLM, this paper proposes a split point procedure based on the explicit likelihood in order to save time when searching for the best split for a given splitting variable. A simulation study for non-Gaussian response is performed to assess the computational gain when building GLM trees. We also propose a benchmark on simulated and empirical datasets of GLM trees against CART, conditional inference trees and LM trees in order to identify situations where GLM trees are efficient. This approach is extended to multiway split trees and log-transformed distributions. Making GLM trees possible through a new split point procedure allows us to investigate the use of GLM in ensemble methods. We propose a numerical comparison of GLM forests against other random forest-type approaches. Our simulation analyses show cases where GLM forests are good challengers to random forests.

International audience; This paper considers the pricing of equity-linked life insurance contracts with death and survival benefits in a general model with multiple stochastic risk factors: interest rate, equity, volatility, unsystematic and systematic mortality. We price the equity-linked contracts by assuming that the insurer hedges the risks to reduce the local variance of the net asset value process and requires a compensation for the non-hedgeable part of the liability in the form of an instantaneous standard deviation risk margin. The price can then be expressed as the solution of a system of non-linear partial differential equations. We reformulate the problem as a backward stochastic differential equation with jumps and solve it numerically by the use of efficient neural networks. Sensitivity analysis is performed with respect to initial parameters and an analysis of the accuracy of the approximation of the true price with our neural networks is provided.

We introduce a model of the hyperbolic plane which arises from Thurston's ideas on best Lipschitz maps between surfaces. More precisely, we apply Thurston's theory to the space of Euclidean triangles. We prove that the Lipschitz constant of the unique affine map between two Euclidean triangles induces a metric on the set of isometry classes of the triangles with area 1/ 2. We then prove that this space of triangles together with 2 times its natural metric is isometric to the hyperbolic plane. Our construction is simple and natural and it makes relations between several geometrical ideas. This paper will appear in the journal Expositiones Mathematicae.

International audience; This paper deals with the coupling between one-dimensional heat and wave equations in unbounded subdomains, as a simplified prototype of fluid-structure interaction problems. First we apply appropriate artificial boundary conditions that yield an equivalent problem, but with bounded subdomains, and we carry out the stability analysis for this coupled problem in truncated domains. Then we devise an optimized Schwarz-in-time (or Schwarz Waveform Relaxation) method for the numerical solving of the coupled equations. Particular emphasis is made on the design of optimized transmission conditions. Notably, for this setting, the optimal transmission conditions can be expressed analytically in a very simple manner. This result is illustrated by some numerical experiments.

International audience; The kernel method is an essential tool for the study of generating series of walks in the quarter plane. This method involves equating to zero a certain polynomial-the kernel polynomial-and using properties of the curve-the kernel curve-this defines. In the present paper, we investigate the basic properties of the kernel curve (irreducibility, singularities, genus, uniformization, etc).

In this paper we consider type-preserving representations of the fundamental group of the three--holed projective plane into $\mathrm{PGL}(2, \R) =\mathrm{Isom}(\HH^2)$ and study the connected components with non-maximal euler class. We show that in euler class zero for all such representations there is a one simple closed curve which is non-hyperbolic, while in euler class $\pm 1$ we show that there are $6$ components where all the simple closed curves are sent to hyperbolic elements and $2$ components where there are simple closed curves sent to non-hyperbolic elements. This answer a question asked by Brian Bowditch. In addition, we show also that in most of these components the action of the mapping class group on these non-maximal component is ergodic. In this work, we use an extension of Kashaev's theory of decorated character varieties to the context of non-orientable surfaces., Comment: 25 pages, 6 figures

This paper deals with the extraction of wave features in elastic media. An inverse approach is proposed for the identification of wave dispersion characteristics (e.g. k-space) in one- and two-dimensional structures (1D, 2D). The proposed method is similar to the ESPRIT algorithm and the Prony series method and can be considered as an extension of the latter, specifically when applied to 1D problems. By using a convolution framework, the method is extended to the 2D case for which it allows the estimation of the full k-space by solving a linear problem. The method is called INverse COnvolution MEthod (INCOME). The formulation of INCOME is first detailed and mathematically justified. Both the 1D and 2D cases are detailed and explained. Then several examples are presented for assessing the validity domain of INCOME. These numerical tests clearly show the relevance of INCOME for structured inputs with periodic characteristics ispartof: Journal Of Sound And Vibration vol:520 status: Published online

National audience; The mass transportation approach to multivariate quantiles in Chernozhukov et al. (2017) was modified in Faugeras and Rüschendorf (2017) by a two steps procedure. In the first step, a mass transportation problem from a spherical reference measure to the copula is solved and combined in the second step with a marginal quantile transformation in the sample space. Also, generalized quantiles given by suitable Markov morphisms are introduced there.In the present paper, this approach is further extended by a functional approach in terms of membership functions, and by the introduction of randomized quantile regions. In addition, in the case of continuous marginals, a smoothed version of the empirical quantile regions is obtained by smoothing the empirical copula. All three extended approaches give empirical quantile ares of exact level and improved stability. The resulting depth areas give a valid representation of the central quantile areas of a multivariate distribution and provide a valuable tool for their analysis.

This paper is devoted to the 2D gravity-capillary water waves equations in their Hamiltonian formulation, addressing the general question of proving Morawetz inequalities. We continue the analysis initiated in our previous work, where we have established local energy decay estimates for gravity waves. Here we add surface tension and prove a stronger estimate with a local regularity gain, akin to the smoothing effect for dispersive equations. Our main result holds globally in time and holds for genuinely nonlinear waves, since we are only assuming some very mild uniform Sobolev bounds for the solutions. Furthermore, it is uniform both in the infinite depth limit and the zero surface tension limit., Comment: 33 pages; this article is based on and continues the authors' work from arXiv:1806.08443

In the classic prophet inequality, a well-known problem in optimal stopping theory, samples from independent random variables (possibly differently distributed) arrive online. A gambler who knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet that sees all the realizations in advance gets. In the late seventies, Krengel and Sucheston (Bull Am Math Soc 83(4):745–747, 1977), established that this worst case ratio is 0.5. A particularly interesting variant is the so-called prophet secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms are known to achieve a constant of $$1-1/e \approx 0.632$$ and very recently this barrier was slightly improved by Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018). In this paper we introduce a new type of multi-threshold strategy, called blind strategy. Such a strategy sets a nonincreasing sequence of thresholds that depends only on the distribution of the maximum of the random variables, and the gambler stops the first time a sample surpasses the threshold of the stage. Our main result shows that these strategies can achieve a constant of 0.669 for the prophet secretary problem, improving upon the best known result of Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018), and even that of Beyhaghi et al. (Improved approximations for posted price and second price mechanisms. CoRR arXiv:1807.03435 , 2018) that works in the case in which the gambler can select the order of the samples. The crux of the result is a very precise analysis of the underlying stopping time distribution for the gambler’s strategy that is inspired by the theory of Schur-convex functions. We further prove that our family of blind strategies cannot lead to a constant better than 0.675. Finally we prove that no algorithm for the gambler can achieve a constant better than $$\sqrt{3}-1 \approx 0.732$$ , which also improves upon a recent result of Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018). This implies that the upper bound on what the gambler can get in the prophet secretary problem is strictly lower than what she can get in the i.i.d. case. This constitutes the first separation between the prophet secretary problem and the i.i.d. prophet inequality.

International audience; In this paper, we conduct a thorough mathematical analysis of the unified formulation advocated by Lauser et al. [Adv. Water Res. 34 (2011), 957-966] for compositional multiphase flows in porous media. The interest of this formulation lies in its potential to automatically handle the appearance and disappearance of phases. However, its practical implementation turned out to be not always robust for realistic fugacity laws associated with cubic equations of state, as shown by Ben Gharbia and Flauraud [Oil & Gas Sci. Technol. 74 (2019), 43]. By focusing on the subproblem of phase equilibrium, we derive sufficient conditions for the existence of the corresponding system of equations. We trace back the difficulty of cubic laws to a deficiency of the Gibbs functions that comes into play due to the "unifying" feature of the new formulation. We propose a partial remedy for this problem by extending the domain of definition of these functions in a natural way. Besides, we highlight the crucial but seemingly unknown fact that the unified formulation encapsulates all the properties known to physicists on phase equilibrium, such as the tangent plane criterion and the minimization of the Gibbs energy of the mixture.; Dans cet article, nous effectuons une analyse mathématique approfondie de la formulation unifiée préconisée par Lauser et al. [Adv. Water Res. 34 (2011), 957--966] pour les écoulements polyphasiques compositionnels en milieu poreux. L'intérêt de cette formulation réside dans sa capacité à gérer automatiquement l'apparition et la disparition des phases. Cependant, sa mise en œuvre pratique s'est avérée ne pas toujours être robuste pour les lois de fugacité réalistes associées à des équations d'état cubiques, comme le montrent Ben Gharbia et Flauraud [Oil & Gas Sci. Technol. 74 (2019), 43]. En se concentrant sur le sous-problème de l'équilibre des phases, nous obtenons des conditions suffisantes pour l'existence du système d'équations correspondant. Nous identifions la difficulté des lois cubiques comme un défaut inhérent aux fonctions de Gibbs associées qu'active malheureusement l'action "unificatrice'' de la nouvelle formulation. Nous proposons un remède partiel à ce problème en étendant le domaine de définition de ces fonctions de manière naturelle. En outre, nous mettons en avant le fait crucial mais apparemment inconnu qu'à partir de la formulation unifiée, on peut déduire toutes les propriétés connues des physiciens sur l'équilibre des phases, telles que le critère du plan tangent et la minimisation de l'énergie de Gibbs du mélange.

International audience; The present paper is devoted to the convergence analysis of a class of asymptotic preserving particle schemes [Filbet & Rodrigues, SIAM J. Numer. Anal., 54 (2) (2016)] for the Vlasov equation with a strong external magnetic field. In this regime, classical Particle-In-Cell (PIC) methods are subject to quite restrictive stability constraints on the time and space steps, due to the small Larmor radius and plasma frequency. The asymptotic preserving discretization that we are going to study removes such a constraint while capturing the large-scale dynamics, even when the discretization (in time and space) is too coarse to capture fastest scales. Our error bounds are explicit regarding the discretization, stiffness parameter, initial data and time.

The paper is devoted to the mathematical analysis of the Cauchy problem for general cross-diffusion systems without any assumption about its entropic structure. A global existence result of nonnegative solutions is obtained by applying a classical Schauder fixed point theorem. The proof is upgraded for enhancing the regularity of the solution, namely its gradient belongs to the space L r ( ( 0 , T ) × Ω ) for some r > 2 . To this aim, the Schauder's strategy is coupled with an extension of Meyers regularity result for linear parabolic equations. We show how this approach allows to prove the well-posedness of the problem using only assumptions prescribing and admissibility range for the ratios between the diffusion and cross-diffusion coefficients. The results are compared with those that are reachable with an additional regularity assumption on the parabolic operator, namely a small BMO assumption for its coefficients. Finally, the question of the maximal principle is also addressed, especially when source terms are incorporated in the equation in order to ensure the confinement of the solution.

Black Sigatoka Disease, also called Black Leaf Streak Disease (BLSD), is caused by the fungus Mycosphaerella fijiensis and is arguably one of the most important pathogens affecting the banana and plantain industries. Theoretical results on its dynamics are rare, even though theoretical descriptions of epidemics of plant diseases are valuable steps toward their efficient management. In this paper, we propose a mathematical model describing the dynamics of BLSD on banana or plantain leaves within a whole field of plants. The model consists of a system of periodic non-autonomous differential equations with a time delay that accounts for the time of incubation ofM. fijiensis’ spores. We compute the basic reproduction number of the disease and show that it does not depend on the time delay, meaning that the persistence of BLSD would not qualitatively change even if the incubation period of the pathogen is perturbed. We derive local and global long-term dynamics of the disease and provide numerical simulations to illustrate our results.

We prove a number of conjectures [arXiv:2005.04066] recently stated by P. Barry, related to the paperfolding sequence and the Rueppel sequence., this supersedes also the paper arXiv:2006.04708

We state and prove that a certain class of smooth functions said to be BH-separable is a meagre subset for the Fr\'echet topology. Because these functions are the only admissible Hamiltonians for Arnold-Liouville systems admitting a bi-Hamiltonian structure, we get that, generically, Arnold-Liouville systems cannot be bi-Hamiltonian. At the end of the paper, we determine, both as a concrete representation of our general result and as an illustrative list, which polynomial Hamiltonians $H$ of the form $H(x,y)=xy+ax^3+bx^2y+cxy^2+dy^3$ are BH-separable.

This paper proposes and studies the notion of interaction between two criteria in a 2-maxitive Sugeno integral model. Within the framework of binary alternatives, we give a necessary and sufficient condition for preferential information on binary alternatives to be representable by a 2-maxitive Sugeno integral model. Using this condition, we show that it is always possible to choose a numerical representation, for which all the interaction indices are strictly positive. Outside the framework of binary alternatives, by introducing binary variables, we propose a MILP allowing to test whether an ordinal preference information is representable by a 2-maxitive Sugeno integral model and whether the interpretation of the interaction indices is ambiguous or not. We illustrate our results with examples.

International audience; Interpolation inequalities play an essential role in Analysis with fundamental consequences in Mathematical Physics, Nonlinear Partial Differential Equations (PDEs), Markov Processes, etc., and have a wide range of applications in various other areas of Science. Research interests have evolved over the years: while mathematicians were originally focussed on abstract properties (for instance appropriate notions of functional spaces for the existence of weak solutions in PDEs), more qualitative questions (for instance, bifurcation diagrams, multiplicity of the solutions in PDEs and their qualitative behaviour) progressively emerged. The use of entropy methods in nonlinear PDEs is a typical example: in some cases, the optimal constant in the inequality can be interpreted as an optimal rate of decay of an entropy for an associated evolution equation. Much more has been learned by adopting this point of view. This paper aims at illustrating some of these recent aspect of entropyentropy production inequalities, with applications to stability in Gagliardo-Nirenberg-Sobolev inequalities and symmetry results in Caffarelli-Kohn-Nirenberg inequalities. Entropy methods provide a framework which relates nonlinear regimes with their linearized counterparts. This framework allows to prove optimality results, symmetry results and stability estimates. Some emphasis will be put on the hidden structure which explain such properties. Related open problems will be listed.

International audience; Let S = {K1,3, K3, P4} be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any non-empty S ⊆ S. The problem is known to be NP-complete for any possible choice of S in general graphs. In this paper, we assume that the input graph is subcubic (i.e. all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S. We identify all polynomial and NP-complete problems in that setting.

This paper is concerned with volume-constrained minimization problems derived from Gamow's liquid drop model for the atomic nucleus, involving the competition of a perimeter term and repulsive nonlocal potentials. We consider a large class of potentials, given by general radial nonnegative kernels which are integrable on $\mathbb{R}^n$, such as Bessel potentials, and study the behavior of the problem for large masses (i.e., volumes). Contrarily to the small mass case, where the nonlocal term becomes negligible compared to the perimeter, here the nonlocal term explodes compared to it. However, using the integrability of those kernels, we rewrite the problem as the minimization of the difference between the classical perimeter and a nonlocal perimeter, which converges to a multiple of the classical perimeter as the mass goes to infinity. Renormalizing to a fixed volume, we show that, if the first moment of the kernels is smaller than an explicit threshold, the problem admits minimizers of arbitrarily large mass, which contrasts with the usual case of Riesz potentials. In addition, we prove that, any sequence of minimizers converges to the ball as the mass goes to infinity. Finally, we study the stability of the ball, and show that our threshold on the first moment of the kernels is sharp in the sense that large balls go from stable to unstable. A direct consequence of the instability of large balls above this threshold is that there exist nontrivial compactly supported kernels for which the problems admit minimizers which are not balls, that is, symmetry breaking occurs., Accepted version. 41 pages

International audience; This paper revisits the modal truncation from an optimisation point of view. In particular, the concept of dominant poles is formulated with respect to different systems norms as the solution of the associated optimal modal truncation problem. The latter is reformulated as an equivalent convex integer or mixed-integer program. Numerical examples highlight the concept and optimisation approach.

International audience; In this paper we consider multi-dimensional partial differential equations of parabolic type involving divergence form operators that possess a discontinuous coefficient matrix along some smooth interface. The solution of the equation is assumed to present a compatibility transmission condition of its conormal derivatives at this interface (multi-dimensional diffraction problem). We prove an existence and uniqueness result for the solution and construct a low complexity numerical Monte Carlo stochastic Euler scheme to approximate the solution of the parabolic partial differential equation in divergence form. In particular, we give new estimates for the partial derivatives of the solution. Using these estimates, we prove a convergence rate for our stochastic numerical method when the initial condition belongs to an iterated domain of the divergence form operator. Our method presents the same convergence rate as the stochastic numerical schemes elaborated for the same problem in the one-dimensional context. Finally, we compare our results to classical deterministic numerical approximations and illustrate the accuracy of our method.

It has been observed in recent works that, for several classes of linear time-invariant time-delay systems of retarded or neutral type with a single delay, if a root of its characteristic equation attains its maximal multiplicity, then this root is the rightmost spectral value, and hence it determines the exponential behavior of the system, a property usually referred to as multiplicity-induced-dominancy (MID). In this paper, we investigate the MID property for one of the simplest cases of systems with two delays, a scalar delay-differential equation of first order with two delayed terms of order zero. We discuss the standard approach based on the argument principle for establishing the MID property for single-delay systems and some of its limitations in the case of our simple system with two delays, before proposing a technique based on crossing imaginary roots that allows to conclude that the MID property holds in our setting., Comment: 16th IFAC Workshop on Time Delay Systems (IFAC TDS 2021)

The dynamics of a low-energy charged particle in an axis-symmetric magnetic field is known to be a regular superposition of periodic—although possibly incommensurate—motions. The projection of the particle orbit along the two non-ignorable coordinates (x,y) may be expressed in terms of each other: y=y(x), yet—to our knowledge—such a functional relation has never been directly produced in literature, but only by way of a detour: first, equations of motion are solved, yielding x=x(t),y=y(t), and then one of the two relations is inverted, x(t)→t(x). In this paper, we present a closed-form functional relation which allows us to express coordinates of the particle’s orbit without the need to pass through the hourly law of motion.

Posted price mechanisms (PPM) constitute one of the predominant practices to price goods in online marketplaces and their revenue guarantees have been a central object of study in the last decade. We consider a basic setting where the buyers' valuations are independent and identically distributed and there is a single unit on sale. It is well-known that this setting is equivalent to the so-called i.i.d. prophet inequality, for which optimal guarantees are known and evaluate to 0.745 in general (equivalent to a PPM with dynamic prices) and $1 - 1/e \approx 0.632$ in the fixed threshold case (equivalent to a fixed price PPM). In this paper we consider an additional assumption, namely, that the underlying market is very large. This is modeled by first fixing a valuation distribution F and then making the number of buyers grow large, rather than considering the worst distribution for each possible market size. In this setting Kennedy and Kertz [Ann. Probab. 1991] breaks the 0.745 fraction achievable in general with a dynamic threshold policy. We prove that this large market benefit continue to hold when using fixed price PPMs, and show that the guarantee of 0.632 actually improves to 0.712. We then move to study the case of selling k identical units and we prove that the revenue gap of the fixed price PPM approaches $1-1/\sqrt{ 2k\pi}$. As this bound is achievable without the large market assumption, we obtain the somewhat surprising result that the large market advantage vanishes as $k$ grows., Comment: Preparing full version

Parallel black box optimization consists in estimating the optimum of a function using $\lambda$ parallel evaluations of $f$. Averaging the $\mu$ best individuals among the $\lambda$ evaluations is known to provide better estimates of the optimum of a function than just picking up the best. In continuous domains, this averaging is typically just based on (possibly weighted) arithmetic means. Previous theoretical results were based on quadratic objective functions. In this paper, we extend the results to a wide class of functions, containing three times continuously differentiable functions with unique optimum. We prove formal rate of convergences and show they are indeed better than pure random search asymptotically in $\lambda$. We validate our theoretical findings with experiments on some standard black box functions.

International audience; We offer a closed form bound on the m-Bézout bound for multi-homogeneous systems whose equations include two variable subsets of the same degree. Our bound is expectedly not tight, since computation of the m-Bézout number is P-hard by reduction to the permanent. On the upside, our bound is tighter than the existing closed-form bound derived from the permanent, which applies only to systems characterized by further structure. Our work is inspired by the application of the m-Bézout bound to counting Euclidean embeddings of distance graphs. Distance geometry and rigidity theory study graphs with a finite number of configurations, up to rigid transformations, which are prescribed by the edge lengths. Counting embeddings is an algebraic question once one constructs a system whose solutions correspond to the different embeddings. Surprisingly, the best asymptotic bound on the number of embeddings had for decades been Bézout's, applied to the obvious system of quadratic equations expressing the length constraints. This is essentially , for graphs of n vertices in d dimensions, and implies a bound of for the most famous case of Laman graphs in the plane. However, the best lower bound is about , which follows by numerically solving appropriate instances. In [3], the authors leverage the m-Bézout bound and express it by the number of certain constrained orientations of simple graphs. A combinatorial process on these graphs has recently improved the bound on orientations and, therefore, has improved the bounds on the number of distance graph embeddings [4]. For Laman graphs the new bound is inferior to thus improving upon Bézout's bound for the first time. In this paper, we obtain a closed-form bound on the m-Bézout number of a class of multi-homogeneous systems that subsumes the systems encountered in distance graph embeddings.

In the paper we consider a finite-volume approximation for the Cahn-Hilliard equation with dynamic boundary conditions. We prove an error estimate for the fully-discrete scheme. The convergence of the scheme is proved in Nabet (IMA J Numer Anal 36(4): 1898–1942, 2016), we prove here an error estimate for the fully-discrete scheme. We also give numerical simulations which validate the theoretical result.

International audience; This paper is concerned with the Richards equation in a heterogeneous domain, each subdomain of which is homogeneous and represents a rocktype. Our first contribution is to rigorously prove convergence toward a weak solution of cell-centered finite-volume schemes with upstream mobility and without Kirchhoff's transform. Our second contribution is to numerically demonstrate the relevance of locally refining the grid at the interface between subregions, where discontinuities occur, in order to preserve an acceptable first order accuracy for the results computed with the schemes under consideration.

In this paper we analyse geometric multiscale models arising in the description of physiological flows such as blood flow in arteries or air flow in the bronchial tree. The geometrical complexity of the networks in which air/blood flows lead to a classical decomposition in two areas: a truncated 3D geometry corresponding to the largest contribution of the domain, and a 0D part connected to the 3D part, modelling air/blood flows in smaller airways/vessels. The fluid in the 3D part is described by the Stokes or the Navier–Stokes system which is coupled to 0D models orso-calledWindkessel models. The resulting Navier–Stokes–Windkessel coupled system involves Neumann non-local boundary conditions that depends on the considered applications. We first show that the different types of Windkessel models share a similar formalism. Next we derive existence results and stability estimates for the continuous coupled Stokes–Windkessel or Navier–Stokes–Windkessel problem as well as stability estimates for the semi-discretized systems with either implicit or explicit treatment of the boundary conditions. In all the calculations, we pay a special attention to the dependency of the various constants and smallness conditions on the data with respect to the physical and numerical parameters. In particular we exhibit different kinds of behavior depending on the considered 0D model. Moreover even if no energy estimates can be derived in energy norms for the Navier–Stokes–Windkessel system, leading to possible and observed numerical instabilities for large applied pressures, we show that stability estimates for both the continuous and semi-discrete problems, can be obtained in appropriate norms for small enough data by introducing a new well chosen Stokes-like operator. These sufficient stability conditions on the data may give a hint on the order of magnitude of the data enabling stable computations without stabilization method for the problem. Numerical simulations illustrate some of the theoretical results.

International audience; This paper shows that machine learning techniques are very successful at classifying the Russian voiceless non-palatalized fricatives [f], [s], and [ʃ] using a small set of acoustic cues. From a data sample of 6320 tokens of read sentences produced by 40 participants, temporal and spectral measurements are extracted from the full sound, the noise duration, and the middle 30 ms windows. Furthermore, 13 mel-frequency cepstral coefficients (MFCCs) are computed from the middle 30 ms window. Classifiers based on single decision trees, random forests, support vector machines, and neural networks are trained and tested to distinguish between these three fricatives. The results demonstrate that, first, the three acoustic cue extraction techniques are similar in terms of classification accuracy (93% and 99%) but that the spectral measurements extracted from the full frication noise duration result in slightly better accuracy. Second, the center of gravity and the spectral spread are sufficient for the classification of [f], [s], and [ʃ] irrespective of contextual and speaker variation. Third, MFCCs show a marginally higher predictive power over spectral cues (