All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.     

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.     

Quadratic matrix polynomials with Hamiltonian spectrum and oscillatory damped systems

We consider quadratic matrix polynomials of the form L(l) = l²A + elB + CL(\lambda) = \lambda^{2}A + \epsilon\lambda B + C, where e\epsilon is a real parameter, A is positive definite and B and C are symmetric. The main results of the paper are the characterization of the class of symmetric matrices B for which the spectrum of the polynomial is symmetric with respect to the imaginary axis and solutions of the corresponding differential equation oscillate in time. We also extend the results in [2] to allow us to study the asymptotic behaviour of the eigenvalues for large e\epsilon.     

Minimum Resolvable Coverings of K v with Copies of K 4 ? e

Suppose K _v is the complete undirected graph with v vertices and K ₄ − e is the graph obtained from a complete graph K ₄ by removing one edge. Let (K ₄ − e)-MRC(v) denote a resolvable covering of K _v with copies of K ₄ − e with the minimum possible number n(v, K ₄ − e) of parallel classes. It is readily verified that n(v, K₄-e) 3 é2(v-1)/5 ù{n(v, K_4-e) \geq \lceil 2(v-1)/5 \rceil} . In this article, it is proved that there exists a (K ₄ − e)-MRC(v) with é2(v-1)/5 ù{\lceil 2(v-1)/5 \rceil} parallel classes if and only if v ≡ 0 (mod 4) with the possible exceptions of v = 108, 172, 228, 292, 296, 308, 412. In addition, the known results on the existence of maximum resolvable (K ₄ − e)-packings are also improved.     

Group Connectivity of 3-Edge-Connected Chordal Graphs

Let A be a finite abelian group and G be a digraph. The boundary of a function f: E(G)ZA is a function ‘f: V(G)ZA given by ‘f(v)=~_{e leaving v}f(e)m~_{e entering v}f(e). The graph G is A-connected if for every b: V(G)ZA with ~_{v] V(G)} b(v)=0, there is a function f: E(G)ZA{0} such that ‘f=b. In [J. Combinatorial Theory, Ser. B 56 (1992) 165-182], Jaeger et al showed that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̈́. It is conjectured that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̓ and that every 5-edge-connected graph is A-connected, for every abelian group A with |A|́.¶ In this note, we investigate the group connectivity of 3-edge-connected chordal graphs and characterize 3-edge-connected chordal graphs that are A-connected for every finite abelian group A with |A|́.     

Second Neighborhood via First Neighborhood in Digraphs

Let D be a simple digraph without loops or digons. For any v ? V(D) v\in V(D) , the first out-neighborhood N⁺(v) is the set of all vertices with out-distance 1 from v and the second neighborhood N⁺⁺(v) of v is the set of all vertices with out-distance 2 from v. We show that every simple digraph without loops or digons contains a vertex v such that |N⁺⁺(v)| 3 g|N⁺(v)| |N^{++}(v)|\geq\gamma|N^+(v)| , where % = 0.657298... is the unique real root of the equation 2x³ + x² -1 = 0.     

Amenable representations and dynamics of the unit sphere in an infinite-dimensional Hilbert space

We establish a close link between the amenability property of a unitary representation p \pi of a group G (in the sense of Bekka) and the concentration property (in the sense of V. Milman) of the corresponding dynamical system (\Bbb S_p, G) ({\Bbb S}_{\pi}, G) , where \Bbb S_H {\Bbb S}_{\cal H} is the unit sphere the Hilbert space of representation. We prove that p \pi is amenable if and only if either p \pi contains a finite-dimensional subrepresentation or the maximal uniform compactification of (\Bbb S_p ({\Bbb S}_{\pi} has a G-fixed point. Equivalently, the latter means that the G-space (\Bbb S_p, G) ({\Bbb S}_{\pi}, G) has the concentration property: every finite cover of the sphere \Bbb S_p {\Bbb S}_{\pi} contains a set A such that for every e > 0 \epsilon > 0 the e \epsilon -neighbourhoods of the translations of A by finitely many elements of G always intersect. As a corollary, amenability of p \pi is equivalent to the existence of a G-invariant mean on the uniformly continuous bounded functions on \Bbb S_p {\Bbb S}_{\pi} . As another corollary, a locally compact group G is amenable if and only if for every strongly continuous unitary representation of G in an infinite-dimensional Hilbert space H {\cal H} the system (\Bbb S_H, G) ({\Bbb S}_{\cal H}, G) has the property of concentration.     

Complex finitary simple Lie algebras

An algebra is called finitary if it consists of finite-rank transformations of a vector space. We classify finitary simple Lie algebras over an algebraically closed field of zero characteristic. It is shown that any such algebra is isomorphic to one of the following¶ (1) a special transvection algebra \frak t(V,P)\frak t(V,\mit\Pi );¶ (2) a finitary orthogonal algebra \frak fso (V,q)\frak {fso} (V,q); ¶ (3) a finitary symplectic algebra \frak fsp (V,s)\frak {fsp} (V,s).¶Here V is an infinite dimensional K-space; q (respectively, s) is a symmetric (respectively, skew-symmetric) nondegenerate bilinear form on V; and P\Pi is a subspace of the dual V^* whose annihilator in V is trivial: 0={v ? V | Pv=0}0=\{{v}\in V\mid \Pi {v}=0\}.     

Efficient Testing of Large Graphs

Let P be a property of graphs. An e\epsilon -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than en²\epsilon n^2 edges to make it satisfy P. The property P is called testable, if for every e\epsilon there exists an e\epsilon -test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [8] showed that certain individual graph properties, like k-colorability, admit an e\epsilon -test. In this paper we make a first step towards a complete logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type ``"$\forall \exists ' are always testable, while we show that some properties containing this alternation are not.     

Propagation Properties for Schrödinger Operators Affiliated with Certain C*-Algebras

We consider anisotropic Schrödinger operators H = -D + V H = -{\Delta} + V in L²(\mathbbRⁿ) L^{2}(\mathbb{R}^n) . To certain asymptotic regions F we assign asymptotic Hamiltonians H_F such that (a) s(H_F) ì s_ess(H) \sigma(H_F) \subset \sigma_{\textrm{ess}}(H) , (b) states with energies not belonging to s(H_F) \sigma(H_F) do not propagate into a neighbourhood of F under the evolution group defined by H. The proof relies on C*-algebra techniques. We can treat in particular potentials that tend asymptotically to different periodic functions in different cones, potentials with oscillation that decays at infinity, as well as some examples considered before by Davies and Simon in [4].     

Linear groups over a skew field of quaternions containing the group T_{n}(A, \Phi) over a subsfield

We study the subgroups of GL_n(D) (n \geqq 3) GL_{n}(D) (n \geqq 3) over a skew field of quaternions D that comprise the subgroup of the unitary group U_n(A, F) U_{n}(A, \Phi) over a subsfield A \subseteqq D A \subseteqq D generated by all transvections in U_n(A, F) U_{n}(A, \Phi) .     

Moser's second one-dimensional inequality for a class of integral operators

Suppose that $1 < p < \infty $1 < p < \infty , q=p/(p-1)q=p/(p-1), and for non-negative f ? L^p(-￥ ,￥)f\in L^p(-\infty\! ,\infty ) and any real x we let F(x)-F(0)=ò₀^xf(t) dtF(x)-F(0)=\int _0^xf(t)\ dt; suppose in addition that ò_-￥^￥ F(t)exp(-|t|) dt=0\int\limits _{-\infty }^\infty F(t)\exp (-|t|)\ dt=0. Moser's second one-dimensional inequality states that there is a constant C_pC_p, such that ò_-￥^￥ exp[a |F(x)|^q-|x|]  dx ￡ C_p\int\limits _{-\infty }^\infty \exp [a |F(x)|^q-|x|] \ dx\le C_p for each f with ||f||_p ￡ 1||f||_p\le 1 and every a ￡ 1a\le 1. Moreover the value a = 1 is sharp. We replace the operation connecting f with F by a more general integral operation; specifically we consider non-negative kernels K(t,x) with the property that xK(t,x) is homogeneous of degree 0 in t, x. We state an analogue of the inequality above for this situation, discuss some applications and consider the sharpness of the constant which replaces a.     

On cardinality constrained cycle and path polytopes

Given a directed graph D = (N, A) and a sequence of positive integers ${1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}Given a directed graph D = (N, A) and a sequence of positive integers 1 ￡ c₁ < c₂ < ? < c_m ￡ |N|{1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c _p for some p ? {1,?,m}{p \in \{1,\ldots,m\}}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.     

A generalization of Pincus’ formula and Toeplitz operator determinants

In this paper we prove the following result. Let A and B be bounded linear operator on a Hilbert space such that AB - BA is trace class. Then the operator determinant of e^A e^B e^-A-B e^{A} e^{B} e^{-A-B} is well defined and equals the exponential of \frac12 \frac{1}{2} trace (AB - BA). This generalization of a formula due to Pincus can be applied to find explicit expressions for operator determinants that appear in the theory of Toeplitz operators.     

Spectral Density and Sobolev Inequalities for Pure and Mixed States

We prove some general Sobolev-type and related inequalities for positive operators A of given ultracontractive spectral decay F(l) = ||_cA(]0, l])||_1,￥{F(\lambda) = \vert\vert_{\chi_A}(\left]0, \lambda \right])\vert\vert_{1,\infty}}, without assuming e ^−tA is sub-Markovian. These inequalities hold on functions, or pure states, as usual, but also on mixed states, or density operators in the quantum-mechanical sense. As an illustration, one can relate the Novikov−Shubin numbers of coverings of finite simplicial complexes to the vanishing of the torsion of the ℓ ^p,2-cohomology for some p ≥ 2.     

A note on discrete heat conduction

If the longitudinal line method is applied to the Cauchy problem u_t = u_xx, u(0, x) = u₀(x) with a bounded function u₀, one is led to a linear initial value problem v￠(t)=A v(t), v(0)=wv'(t)=A v(t),\, v(0)=w in l^￥ (\Bbb Z)l^\infty (\Bbb Z). Using Banach limit techniques we study the asymptotic behaviour of the solutions of these problems as t tends to infinity.     

On the number of conjugacy classes of maximal subgroups in a finite soluble group

We show that for many formations \frak F\frak F, there exists an integer n = [`(m)](\frak F)n = \overline m(\frak F) such that every finite soluble group G not belonging to the class \frak F\frak F has at most n conjugacy classes of maximal subgroups belonging to the class \frak F\frak F. If \frak F\frak F is a local formation with formation function f, we bound [`(m)](\frak F)\overline m(\frak F) in terms of the [`(m)](f(p))(p ? \Bbb P )\overline m(f(p))(p \in \Bbb P ). In particular, we show that [`(m)](\frak N^k) = k+1\overline m(\frak N^k) = k+1 for every nonnegative integer k, where \frak N^k\frak N^k is the class of all finite groups of Fitting length ￡ k\le k.     

Bounded solutions of the Golab—Schinzel equation

Summary. Let \Bbb K {\Bbb K} be either the field of reals or the field of complex numbers, X be an F-space (i.e. a Fréchet space) over \Bbb K {\Bbb K} n be a positive integer, and f : X ? \Bbb K f : X \to {\Bbb K} be a solution of the functional equation¶¶f(x + f(x)ⁿ y) = f(x) f(y) f(x + f(x)^n y) = f(x) f(y) .¶We prove that, if there is a real positive a such that the set { x ? X : |f(x)| ? (0, a)} \{ x \in X : |f(x)| \in (0, a)\} contains a subset of second category and with the Baire property, then f is continuous or { x ? X : |f(x)| ? (0, a)} \{ x \in X : |f(x)| \in (0, a)\} for every x ? X x \in X . As a consequence of this we obtain the following fact: Every Baire measurable solution f : X ? \Bbb K f : X \to {\Bbb K} of the equation is continuous or equal zero almost everywhere (i.e., there is a first category set A ì X A \subset X with f(X \A) = { 0 }) f(X \backslash A) = \{ 0 \}) .     

Homogenization for strongly anisotropic nonlinear elliptic equations

In this paper we present homogenization results for elliptic degenerate differential equations describing strongly anisotropic media. More precisely, we study the limit as e? 0 \epsilon \to 0 of the following Dirichlet problems with rapidly oscillating periodic coefficients:¶¶ . \cases {{ -div(\alpha(\frac{x}{\epsilon}}, \nabla u) A(\frac{x}{\epsilon}) \nabla u) = f(x) \in L^{\infty}(\Omega) \atop u = 0 su \eth\Omega\ } ¶¶where, p > 1,     a: \Bbb Rⁿ ×\Bbb Rⁿ ? \Bbb R,     a(y,x) ? áA(y)x,x?^p/2-1, A ? M^{n ×n}(\Bbb R) p>1, \quad \alpha : \Bbb R^n \times \Bbb R^n \to \Bbb R, \quad \alpha(y,\xi) \approx \langle A(y)\xi,\xi \rangle ^{p/2-1}, A \in M^{n \times n}(\Bbb R) , A being a measurable periodic matrix such that A^t(x) = A(x) 3 0A^t(x) = A(x) \ge 0 almost everywhere.¶¶The anisotropy of the medium is described by the following structure hypothesis on the matrix A:¶¶l^2/p(x) |x|² ￡ áA(x)x,x? ￡ L ^2/p(x) |x|², \lambda^{2/p}(x) |\xi|^2 \leq \langle A(x)\xi,\xi \rangle \leq \Lambda ^{2/p}(x) |\xi|^2, ¶¶where the weight functions l \lambda and L \Lambda (satisfying suitable summability assumptions) can vanish or blow up, and can also be "moderately" different. The convergence to the homogenized problem is obtained by a classical compensated compactness argument, that had to be extended to two-weight Sobolev spaces.     

Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold

We show that for every closed Riemannian manifold X there exists a positive number¶ $ \varepsilon_0 > 0 $ \varepsilon_0 > 0 such that for all 0< e\leqq e₀ \varepsilon \leqq \varepsilon_0 there exists some¶ $ \delta > 0 $ \delta > 0 such that for every metric space Y with Gromov-Hausdorff distance to X less than¶ d \delta the geometric e \varepsilon -complex |Y_e| |Y_\varepsilon| is homotopy equivalent to X.¶ In particular, this gives a positive answer to a question of Hausmann [4].