A special case of the Stahl conjecture

Let _Gn,k$G_{n,k}$ denote the Kneser graph whose vertices are the n$n$-element subsets of a (2n+k)$(2n+k)$-element set and whose edges are the disjoint pairs. In this paper we prove that for any non-negative integer s$s$ there is no graph homomorphism from _G4,2$G_{4,2}$ to _G4s+1,2s+1$G_{4s+1,2s+1}$. This confirms a conjecture of Stahl in a special case.     

Bounds on the vertex–edge domination number of a tree

A vertex–edge dominating set of a graph G is a set D of vertices of G such that every edge of G is incident with a vertex of D or a vertex adjacent to a vertex of D. The vertex–edge domination number of a graph G  , denoted by γ_ve(T)${\gamma }_{\mathrm{ve}}(T)$, is the minimum cardinality of a vertex–edge dominating set of G. We prove that for every tree T   of order n?3$n?3$ with l leaves and s   support vertices, we have (n−l−s+3)/4?γ_ve(T)?n/3$(n-l-s+3)/4?{\gamma }_{\mathrm{ve}}(T)?n/3$, and we characterize the trees attaining each of the bounds.     

A k-product uncapacitated facility location problem

A k-product uncapacitated facility location problem can be described as follows. There is a set of demand points where clients are located and a set of potential sites where facilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost determined by the product it intends to supply. There is a non-negative cost of shipping goods between each pair of locations. These costs are assumed to be symmetric and satisfy the triangle inequality. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k   facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, an approximation algorithm within a factor of 2k+1$2k+1$ of the optimum cost is presented. Assuming that fixed setup costs are zero, we give a 2k-1$2k-1$ approximation algorithm for the problem. In addition we show that for the case k=2$k=2$, the problem is NP-complete when the cost structure is general and there is a 2-approximation algorithm when the costs are symmetric and satisfy the triangle inequality. The algorithm is shown to produce an optimal solution if the 2-product uncapacitated facility location problem with no fixed costs happens to fall on a tree graph.     

Disjoint paths in tournaments

Given k   pairs of vertices (_si,_ti)$(s_i,t_i)$(1≤i≤k)$(1\le i\le k)$ of a digraph G, how can we test whether there exist k   vertex-disjoint directed paths from _si$s_i$ to _ti$t_i$ for 1≤i≤k$1\le i\le k$? This is NP-complete in general digraphs, even for k=2$k=2$ [2], but for k=2$k=2$ there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.     

Uniform bound of Sobolev norms of solutions to 3D nonlinear wave equations with null condition

This article concerns the time growth of Sobolev norms of classical solutions to the 3D quasi-linear wave equations with the null condition. Given initial data in H^s×H^s−1$H^s\times H^{s-1}$ with compact supports, the global well-posedness theory has been established independently by Klainerman [13] and Christodoulou [3], respectively, for a relatively large integer s  . However, the highest order Sobolev energy, namely, the H^s$H^s$ energy of solutions may have a logarithmic growth in time. In this paper, we show that the H^s$H^s$ energy of solutions is also uniformly bounded for s?5$s?5$. The proof employs the generalized energy method of Klainerman, enhanced by weighted L²$L^2$ estimates and the ghost weight introduced by Alinhac.     

Generalized cover ideals and the persistence property

Let I   be a square-free monomial ideal in R=k[_x1,…,_xn]$R=k[x_1,\dots ,x_n]$, and consider the sets of associated primes Ass(I^s)$\mathrm{Ass}(I^s)$ for all integers s?1$s?1$. Although it is known that the sets of associated primes of powers of I eventually stabilize, there are few results about the power at which this stabilization occurs (known as the index of stability). We introduce a family of square-free monomial ideals that can be associated to a finite simple graph G that generalizes the cover ideal construction. When G   is a tree, we explicitly determine Ass(I^s)$\mathrm{Ass}(I^s)$ for all s?1$s?1$. As consequences, not only can we compute the index of stability, we can also show that this family of ideals has the persistence property.     

Minimum degree and disjoint cycles in generalized claw-free graphs

For s≥3$s\ge 3$ a graph is _K1,s$K_{1,s}$-free if it does not contain an induced subgraph isomorphic to _K1,s$K_{1,s}$. Cycles in _K1,3$K_{1,3}$-free graphs, called claw-free graphs, have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions to _K1,s$K_{1,s}$-free graphs, normally called generalized claw-free graphs. In particular, we prove that if G$G$ is _K1,s$K_{1,s}$-free of sufficiently large order n=3k$n=3k$ with δ(G)≥n/2+c$\delta \left(G\right)\ge n/2+c$ for some constant c=c(s)$c=c\left(s\right)$, then G$G$ contains k$k$ disjoint triangles. Analogous results with the complete graph _K3$K_3$ replaced by a complete graph _Km$K_m$ for m≥3$m\ge 3$ will be proved. Also, the existence of 2$2$-factors for _K1,s$K_{1,s}$-free graphs with minimum degree conditions will be shown.     

Nowhere-zero 3-flows and modulo k-orientations

The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutte?s 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is _Z3$Z_3$-connected, Jaeger?s circular flow conjecture (1984) that for every odd natural number k?3$k?3$, every (2k−2)$(2k-2)$-edge-connected graph has a modulo k  -orientation, etc. It was proved recently by Thomassen that, for every odd number k?3$k?3$, every (2k²+k)$(2k^2+k)$-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G   is _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassen?s method is refined to prove the following: For every odd number  k?3$k?3$, every  (3k−3)$(3k-3)$-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is  _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs.     

Regularity for the fractional Gelfand problem up to dimension 7

We study the problem (−Δ)^su=λe^u${(-\mathrm{\Delta })}^{s}u=\lambda e^u$ in a bounded domain Ω⊂Rⁿ$\Omega \subset {\mathbb{R}}^n$, where λ   is a positive parameter. More precisely, we study the regularity of the extremal solution to this problem. Our main result yields the boundedness of the extremal solution in dimensions n≤7$n\le 7$ for all s∈(0,1)$s\in (0,1)$ whenever Ω   is, for every i=1,...,n$i=1,...,n$, convex in the _xi$x_i$-direction and symmetric with respect to {_xi=0}$\{x_i=0\}$. The same holds if n=8$n=8$ and s?0.28206...$s?0.28206...$, or if n=9$n=9$ and s?0.63237...$s?0.63237...$. These results are new even in the unit ball Ω=_B1$\Omega =B_1$.     

On the u-invariant of function fields of curves over complete discretely valued fields

Let K be a complete discretely valued field with residue field κ  . If char(K)=0$\mathrm{char}(K)=0$, char(κ)=2$\mathrm{char}(\kappa )=2$ and [κ:κ²]=d$[\kappa :{\kappa }^2]=d$, we prove that there exists an integer N depending on d such that the u-invariant of any function field in one variable over K is bounded by N. The method of proof is via introducing the notion of uniform boundedness for the p-torsion of the Brauer group of a field and relating the uniform boundedness of the 2-torsion of the Brauer group to the finiteness of the u-invariant. We prove that the 2-torsion of the Brauer group of function fields in one variable over K is uniformly bounded.     

Derivations and local derivations on Freudenthal almost f-algebras

Let A be an Archimedean f  -algebra and let N(A)$N(A)$ be the set of all nilpotent elements of A. Colville et al. [4] proved that a positive linear map d:A→A$d:A\to A$ is a derivation if and only if d(A)⊂N(A)$d(A)\subset N(A)$ and d(A²)={0}$d(A^2)=\{0\}$, where A²$A^2$ is the set of all products ab in A.     

Poincaré series of modules over compressed Gorenstein local rings

Given two positive integers e and s we consider Gorenstein Artinian local rings R   whose maximal ideal m$\mathfrak{m}$ satisfies m^s≠0=m^s+1${\mathfrak{m}}^s\ne 0={\mathfrak{m}}^{s+1}$ and _rankR/m(m/m²)=e${\mathrm{rank}}_{R/\mathfrak{m}}(\mathfrak{m}/{\mathfrak{m}}^2)=e$. We say that R is a compressed Gorenstein local ring   when it has maximal length among such rings. It is known that generic Gorenstein Artinian algebras are compressed. If s≠3$s\ne 3$, we prove that the Poincaré series of all finitely generated modules over a compressed Gorenstein local ring are rational, sharing a common denominator. A formula for the denominator is given. When s is even this formula depends only on the integers e and s  . Note that for s=3$s=3$ examples of compressed Gorenstein local rings with transcendental Poincaré series exist, due to Bøgvad.     

Probabilistic properties of number fields

In general a bound on number theoretic invariants under the Generalized Riemann Hypothesis (GRH) for the Dedekind zeta function of a number field K   is much stronger than an unconditional one. In this article, we consider three invariants; the residue of _ζK(s)${\zeta }_K(s)$ at s=1$s=1$, the logarithmic derivative of Artin L-function attached to K   at s=1$s=1$, and the smallest prime which does not split completely in K. We obtain bounds on them just as good as the bounds under GRH except for a density zero set of number fields.     

Continuity properties of the data-to-solution map for the generalized Camassa–Holm equation

This work studies a generalized Camassa–Holm equation with higher order nonlinearities (g-kbCH). The Camassa–Holm, the Degasperis–Procesi and the Novikov equations are integrable members of this family of equations. g-kb  CH is well-posed in Sobolev spaces H^s$H^s$, s>3/2$s>3/2$, on both the line and the circle and its solution map is continuous but not uniformly continuous. In this work it is shown that the solution map is Hölder continuous in H^s$H^s$ equipped with the H^r$H^r$-topology for 0?r<s$0?r<s$, and the Hölder exponent is expressed in terms of s and r.     

Hyperspaces of Keller compacta and their orbit spaces

A compact convex subset K   of a topological linear space is called a Keller compactum if it is affinely homeomorphic to an infinite-dimensional compact convex subset of the Hilbert space _?2${?}_2$. Let G be a compact topological group acting affinely on a Keller compactum K   and let 2^K$2^K$ denote the hyperspace of all non-empty compact subsets of K endowed with the Hausdorff metric topology and the induced action of G  . Further, let cc(K)$cc(K)$ denote the subspace of 2^K$2^K$ consisting of all compact convex subsets of K. In a particular case, the main result of the paper asserts that if K   is centrally symmetric, then the orbit spaces 2^K/G$2^K/G$ and cc(K)/G$cc(K)/G$ are homeomorphic to the Hilbert cube.