Right-convergence of sparse random graphs

The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs \(\mathbb{G }_N, N\ge 1\) to some target graph \(W\) . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151–219, 2012; Borgs et al. in Adv Math 219:1801–1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000–1017, 2011; Lovász and Szegedy in J Comb Theory Ser B 96:933–957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with \(W\) . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph \(W\) satisfies a certain convexity property. We treat the case of discrete and continuous target graphs \(W\) . The latter case allows us to prove a special case of Talagrand’s recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from \(\mathbb{R }^N\) by intersecting it with linearly in \(N\) many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71–79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdös-Rényi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535–564, 2003; Franz et al. in J Phys A Math Gen 36:10967–10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221–3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312–336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdös-Rényi graphs for some special cases of \(W\) . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.     

Global symplectic coordinates on gradient Kähler–Ricci solitons

A classical result of McDuff [14] asserts that a simply connected complete Kähler manifold $(M,g,\omega )$ with non positive sectional curvature admits global symplectic coordinates through a symplectomorphism $\Psi \ : M \rightarrow \mathbb{R }^{2n}$ (where $n$ is the complex dimension of $M$ ), satisfying the following property (proved by E. Ciriza in [4]): the image $\Psi (T)$ of any complex totally geodesic submanifold $T\subset M$ through the point $p$ such that $\Psi (p)=0$ , is a complex linear subspace of $\mathbb C ^n\simeq \mathbb{R }^{2n}$ . The aim of this paper is to exhibit, for all positive integers $n$ , examples of $n$ -dimensional complete Kähler manifolds with non-negative sectional curvature globally symplectomorphic to $\mathbb{R }^{2n}$ through a symplectomorphism satisfying Ciriza’s property.     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

Weyl modules and q-Whittaker functions

Let $G$ be a semi-simple simply connected group over $\mathbb {C}$ . Following Gerasimov et al. (Comm Math Phys 294:97–119, 2010) we use the $q$ -Toda integrable system obtained by quantum group version of the Kostant–Whittaker reduction (cf. Etingof in Am Math Soc Trans Ser 2:9–25, 1999, Sevostyanov in Commun Math Phys 204:1–16, 1999) to define the notion of $q$ -Whittaker functions $\varPsi _{\check{\lambda }}(q,z)$ . This is a family of invariant polynomials on the maximal torus $T\subset G$ (here $z\in T$ ) depending on a dominant weight $\check{\lambda }$ of $G$ whose coefficients are rational functions in a variable $q\in \mathbb {C}^*$ . For a conjecturally the same (but a priori different) definition of the $q$ -Toda system these functions were studied by Ion (Duke Math J 116:1–16, 2003) and by Cherednik (Int Math Res Notices 20:3793–3842, 2009) [we shall denote the $q$ -Whittaker functions from Cherednik (Int Math Res Notices 20:3793–3842, 2009) by $\varPsi '_{\check{\lambda }}(q,z)$ ]. For $G=SL(N)$ these functions were extensively studied in Gerasimov et al. (Comm Math Phys 294:97–119, 2010; Comm Math Phys 294:121–143, 2010; Lett Math Phys 97:1–24, 2011). We show that when $G$ is simply laced, the function $\hat{\varPsi }_{\check{\lambda }}(q,z)=\varPsi _{\check{\lambda }}(q,z)\cdot {\prod \nolimits _{i\in I}\prod \nolimits _{r=1}^{\langle \alpha _i,\check{\uplambda }\rangle }(1-q^r)}$ (here $I$ denotes the set of vertices of the Dynkin diagram of $G$ ) is equal to the character of a certain finite-dimensional $G[[{\mathsf {t}}]]\rtimes \mathbb {C}^*$ -module $D(\check{\lambda })$ (the Demazure module). When $G$ is not simply laced a twisted version of the above statement holds. This result is known for $\varPsi _{\check{\lambda }}$ replaced by $\varPsi '_{\check{\lambda }}$ (cf. Sanderson in J Algebraic Combin 11:269–275, 2000 and Ion in Duke Math J 116:1–16, 2003); however our proofs are algebro-geometric [and rely on our previous work (Braverman, Finkelberg in Semi-infinite Schubert varieties and quantum $K$ -theory of flag manifolds, arXiv/1111.2266, 2011)] and thus they are completely different from Sanderson (J Algebraic Combin 11:269–275, 2000) and Ion (Duke Math J 116:1–16, 2003) [in particular, we give an apparently new algebro-geometric interpretation of the modules $D(\check{\lambda })]$ .     

A vanishing result for strictly p-convex domains

In view of Andreotti and Grauert (Bull Soc Math France 90:193–259, 1962) vanishing theorem for \(q\) -complete domains in \(\mathbb C ^{n}\) , we reprove a vanishing result by Sha (Invent Math 83(3):437–447, 1986), and Wu (Indiana Univ Math J 36(3):525–548, 1987), for the de Rham cohomology of strictly \(p\) -convex domains in \(\mathbb R ^n\) in the sense of Harvey and Lawson (The foundations of \(p\) -convexity and \(p\) -plurisubharmonicity in riemannian geometry. arXiv:1111.3895v1 [math.DG]). Our proof uses the \({L}^2\) -techniques developed by Hörmander (An introduction to complex analysis in several variables, 3rd edn. North-Holland Publishing Co, Amsterdam 1990), and Andreotti and Vesentini (Inst Hautes Études Sci Publ Math 25:81–130, 1965).     

A note on the uniqueness problem of non-Archimedean holomorphic curves

We prove a uniqueness theorem for non-Archimedean linearly nondegenerate holomorphic curves in projective spaces of dimension $n$ with two families of $(2n+2)$ hyperplanes in general position. Our result strongly generalizes the uniqueness theorem with $(3n+1)$ hyperplanes of Ru in [11].     

A tableau formula for eta polynomials

We use the Pieri and Giambelli formulas of Buch et al. (Invent Math 178:345–405, 2009; J Reine Angew, 2013) and the calculus of raising operators developed in Buch et al. (A Giambelli formula for isotropic Grassmannians, arXiv:0811.2781, 2008) and Tamvakis (J Reine Angew Math 652, 207–244, 2011) to prove a tableau formula for the eta polynomials of Buch et al. (J Reine Angew, 2013) and the Stanley symmetric functions which correspond to Grassmannian elements of the Weyl group $\widetilde{W}_n$ of type $\text {D}_n$ . We define the skew elements of $\widetilde{W}_n$ and exhibit a bijection between the set of reduced words for any skew $w\in \widetilde{W}_n$ and a set of certain standard typed tableaux on a skew shape $\lambda /\mu $ associated to $w$ .     

Uniqueness of minimal Fourier-type extensions in L_1-spaces

We give a characterization of uniqueness of finite rank Fourier-type minimal extensions in $L_1$ -norm. This generalizes the main result obtained by Lewicki (Proceedings of the Fifth International Conference on Function Spaces, Lecture Notes in Pure and Applied Mathematics, vol. 213, pp. 337–345, 1998) to the case of $n$ -circular sets in $\mathbb{C }^n$ .     

A ternary additive problem

The problem of representing a large integer $n$ in the form $n=m^2+x^3+y^5$ has been studied by a number of authors in the past decades. In this paper, we restrict $m$ to square-free integers, and $x, y$ to primes, and show that there is such a representation for all $n\le N$ with at most $O(N^{1-\frac{1}{45}+\varepsilon })$ exceptions. We also improve the recent results of Liu (Acta Math Hungar 130(1–2):118–139, 2011) and Bauer (J Math 38(4):1073–1090, 2008) on related problems.     

A refined stable restriction theorem for vector bundles on quadric threefolds

Let \(E\) be a stable rank 2 vector bundle on a smooth quadric threefold \(Q\) in the projective 4-space \(P\) . We show that the hyperplanes \(H\) in \(P\) for which the restriction of \(E\) to the hyperplane section of \(Q\) by \(H\) is not stable form, in general, a closed subset of codimension at least 2 of the dual projective 4-space, and we explicitly describe the bundles \(E\) which do not enjoy this property. This refines a restriction theorem of Ein and Sols (Nagoya Math J 96:11–22, 1984) in the same way the main result of Coand? (J Reine Angew Math 428:97–110, 1992) refines the restriction theorem of Barth (Math Ann 226:125–150, 1977).     

Complement of forms

The notions of the parallel sum, the parallel difference, and the complement of two nonnegative sesquilinear forms were introduced and studied by Hassi, Sebestyé and de Snoo in Hassi et al. (Oper Theory Adv Appl 198:211–227, 2010) and Hassi et al. (J Funct Anal 257(12):3858–3894, 2009). In this paper we continue these investigations. The Galois correspondence induced by the map ${\mathfrak{m} \mapsto \mathfrak{m}_\mathfrak{t}}$ (where ${\mathfrak{m}_\mathfrak{t}}$ denotes the ${\mathfrak{t}}$ -complement of ${\mathfrak{m}}$ ) is also studied. Inspired by the work of Eriksson and Leutwiler Eriksson and Leutwiler (Math Ann 274:301–317, 1986), we introduce the notion of quasi-unit for nonnegative sesquilinear forms. The quasi-units are characterized by means of the complement and the disjoint part. It is also shown that the ${{\mathfrak{t}}}$ -quasi-units coincide with the extreme points of the convex set ${\mathfrak{z}: 0 \leq \mathfrak{z} \leq \mathfrak{t}\}}$ .     

Preemptive and non-preemptive generalized min sum set cover

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given $n$ ground elements and a collection of sets $\mathcal{S }= \{S_1, S_2, \ldots , S_m\}$ where each set $S_i \in 2^{[n]}$ has a positive requirement $\kappa (S_i)$ that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set $S_i$ is defined as the first index $j$ in the ordering such that the first $j$ elements in the ordering contain $\kappa (S_i)$ elements in $S_i$ . This problem was introduced by Azar et al. (2009) with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known by Bansal et al. (2010) and Skutella and Williamson (Oper Res Lett 39(6):433–436, 2011). We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set $S$ is covered in the moment when $\kappa (S)$ amount of elements in $S$ are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming relaxation and analysis are completely different from the aforementioned previous works. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved $12.4$ -approximation for the non-preemptive problem.     

On the Li coefficients for the Dirichlet L-functions

In this paper, we prove under the Riemann hypothesis that the Li coefficients for the Dirichlet $L$ -functions $\lambda _{\chi }(n)$ are increasing in $n$ . We also prove unconditionally that the first Li coefficients are increasing using the Bell polynomials. Furthermore, we give a probabilistic interpretation and describe another method differently as stated in Omar et al. (LMS J Comput Math 14:140–154, 2011) to compute them.     

Harmonic mappings in Bergman spaces

In this paper, we investigate the properties of mappings in harmonic Bergman spaces. First, we discuss the coefficient estimate, the Schwarz-Pick Lemma and the Landau-Bloch theorem for mappings in harmonic Bergman spaces in the unit disk $\mathbb D $ of $\mathbb C $ . Our results are generalizations of the corresponding ones in Chen et al. (Proc Am Math Soc 128:3231–3240, 2000), Chen et al. (J Math Anal Appl 373:102–110, 2011), Chen et al. (Ann Acad Sci Fenn Math 36:567–576, 2011). Then, we study the Schwarz-Pick Lemma and the Landau-Bloch theorem for mappings in harmonic Bergman spaces in the unit ball $\mathbb B ^{n}$ of $\mathbb C ^{n}$ . The obtained results are generalizations of the corresponding ones in Chen and Gauthier (Proc Am Math Soc 139:583–595 2011). At last, we get a characterization for mappings in harmonic Bergman spaces on $\mathbb B ^{n}$ in terms of their complex gradients.     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

Additive Results of the Drazin Inverse for Bounded Linear Operators

Given two bounded linear operators $P$ and $Q$ on a Banach space the formula for the Drazin inverse of $P+Q$ is given, under the assumptions $P^2 Q+PQ^2=0$ and $P^3 Q=PQ^3=0$ . In particular, some recent results arising in Drazin (Am Math Mon 65:506–514, 1958), Hartwig et al. (Linear Algebra Appl 322:207–217, 2001) and Castro-González et al. (J Math Anal Appl 350:207–215, 2009) are extended.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

The homotopy of the K(2)-local Moore spectrum at the prime 3 revisited

In this paper we use the approach introduced in (Goerss et al., Ann Math 162(2):777–822, 2005) in order to analyze the homotopy groups of $L_{K(2)}V(0)$ , the mod- $3$ Moore spectrum $V(0)$ localized with respect to Morava $K$ -theory $K(2)$ . These homotopy groups have already been calculated by Shimomura (J Math Soc Japan 52(1): 65–90, 2000). The results are very complicated so that an independent verification via an alternative approach is of interest. In fact, we end up with a result which is more precise and also differs in some of its details from that of Shimomura (J Math Soc Japan 52(1): 65–90, 2000). An additional bonus of our approach is that it breaks up the result into smaller and more digestible chunks which are related to the $K(2)$ -localization of the spectrum $TMF$ of topological modular forms and related spectra. Even more, the Adams–Novikov differentials for $L_{K(2)}V(0)$ can be read off from those for $TMF$ .     

On the Brauer-Feit bound for abelian defect groups

We improve the Brauer-Feit bound on the number of irreducible characters in a $p$ -block for abelian defect groups by making use of Halasi and Podoski (Every coprime linear group admits a base of size two. http://arxiv.org/abs/1212.0199v1, [7]) and Kessar and Malle (Ann Math 178(2):321–384, [11]). We also prove Brauer’s $k(B)$ -Conjecture for 2-blocks with abelian defect groups of rank at most 5 and 3-blocks and 5-blocks with abelian defect groups of rank at most 3.