Recognizing conic TDI systems is hard

In this note we prove that the problem of deciding whether or not a set of integer vectors forms a Hilbert basis is co-NP-complete. Equivalently, deciding whether a conic linear system is totally dual integral or not, is co-NP-complete. These statements are true even if the vectors in the set or respectively the coefficient vectors of the inequalities are 0?C1 vectors having at most three ones.     

Positive and sign-changing clusters around saddle points of the potential for nonlinear elliptic problems

We study the existence and asymptotic behavior of positive and sign-changing multipeak solutions for the equation $$ -\varepsilon^2\Delta v+V(x)v=f(v)\quad{\rm in}\,\,\,\mathbb{R}^N, $$ where ?? is a small positive parameter, f a superlinear, subcritical and odd nonlinearity, V a uniformly positive potential. No symmetry on V is assumed. It is known (Kang and Wei in Adv Differ Equ 5:899?C928, 2000) that this equation has positive multipeak solutions with all peaks approaching a local maximum of V. It is also proved that solutions alternating positive and negative spikes exist in the case of a minimum (see D??Aprile and Pistoia in Ann Inst H. Poincaré Anal Non Linéaire 26:1423?C1451, 2009). The aim of this paper is to show the existence of both positive and sign-changing multipeak solutions around a nondegenerate saddle point of V.     

Tur��n��s extremal problem on locally compact abelian groups

Let G be a locally compact abelian group (LCA group) and ?? be an open, 0-symmetric set. Let F:= F(??) be the set of all continuous functions f: G ?? ? which are supported in ?? and are positive definite. The Turán constant of ?? is then defined as $$ \mathcal{T}(\Omega ): = \sup \left\{ {\int_\Omega {f:f \in \mathcal{F}} (\Omega ),f(0) = 1} \right\} $$ . Mihalis Kolountzakis and the author has shown that structural properties ?? like spectrality, tiling or packing with a certain set ?? ?? of subsets ?? in finite, compact or Euclidean (i.e., ? ^d ) groups and in ? ^d yield estimates of T (??). However, in these estimates some notion of the size, i.e., density of ?? played a natural role, and thus in groups where we had no grasp of the notion, we could not accomplish such estimates. In the present work a recent generalized notion of asymptotic uniform upper density is invoked, allowing a more general investigation of the Turán constant in relation to the above structural properties. Our main result extends a result of Arestov and Berdysheva, (also obtained independently and along different lines by Kolountzakis and the author), stating that convex tiles of a Euclidean space necessarily have $$ \mathcal{T}_{\mathbb{R}^d } (\Omega )\left| \Omega \right|/2^d $$ . In our extension ? ^d could be replaced by any LCA group, convexity is considerably relaxed to ?? being a difference set, and the condition of tiling is also relaxed to a certain packing type condition and positive asymptotic uniform upper density of the set ??. Also our goal is to give a more complete account of all the related developments and history, because until now an exhaustive overview of the full background of the so-called Turán problem was not delivered.     

Quasi-stationary distributions for structured birth and death processes with mutations

We study the probabilistic evolution of a birth and death continuous time measure-valued process with mutations and ecological interactions. The individuals are characterized by (phenotypic) traits that take values in a compact metric space. Each individual can die or generate a new individual. The birth and death rates may depend on the environment through the action of the whole population. The offspring can have the same trait or can mutate to a randomly distributed trait. We assume that the population will be extinct almost surely. Our goal is the study, in this infinite dimensional framework, of the quasi-stationary distributions of the process conditioned on non-extinction. We first show the existence of quasi-stationary distributions. This result is based on an abstract theorem proving the existence of finite eigenmeasures for some positive operators. We then consider a population with constant birth and death rates per individual and prove that there exists a unique quasi-stationary distribution with maximal exponential decay rate. The proof of uniqueness is based on an absolute continuity property with respect to a reference measure.     

Eigenvectors of some large sample covariance matrix ensembles

We consider sample covariance matrices ${S_N=\frac{1}{p}\Sigma_N^{1/2}X_NX_N^* \Sigma_N^{1/2}}$ where X _N is a N ×? p real or complex matrix with i.i.d. entries with finite 12th moment and ?? _N is a N ×? N positive definite matrix. In addition we assume that the spectral measure of ?? _N almost surely converges to some limiting probability distribution as N ?? ?? and p/N ?? ?? >?0. We quantify the relationship between sample and population eigenvectors by studying the asymptotics of functionals of the type ${\frac{1}{N}\text{Tr} ( g(\Sigma_N) (S_N-zI)^{-1}),}$ where I is the identity matrix, g is a bounded function and z is a complex number. This is then used to compute the asymptotically optimal bias correction for sample eigenvalues, paving the way for a new generation of improved estimators of the covariance matrix and its inverse.     

Number of distinct sites visited by a random walk with internal states

In the classical paper of Dvoretzky and Erd?s (Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, pp 353?C367, 1951), asymptotics for the expected value and the variance of the number of distinct sites visited by a Simple Symmetric Random Walk were calculated. Here, these results are generalized for Random Walks with Internal States. Moreover, both weak and strong laws of large numbers are proved. As a tool for these results, the error term of the local limit theorem in Krámli and Szász (Zeitschrift Wahrscheinlichkeitstheorie verw Gebiete 63:85?C95, 1983) is also estimated.     

Poisson process Fock space representation, chaos expansion and covariance inequalities

We consider a Poisson process ?? on an arbitrary measurable space with an arbitrary sigma-finite intensity measure. We establish an explicit Fock space representation of square integrable functions of ??. As a consequence we identify explicitly, in terms of iterated difference operators, the integrands in the Wiener?CIt? chaos expansion. We apply these results to extend well-known variance inequalities for homogeneous Poisson processes on the line to the general Poisson case. The Poincaré inequality is a special case. Further applications are covariance identities for Poisson processes on (strictly) ordered spaces and Harris?CFKG-inequalities for monotone functions of ??.     

On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.