Extension theorems for functional equations with bisymmetric operations

Summary. In this paper we deal with the extension of the following functional equation¶¶ f (x) = M (f (m₁(x, y)), ..., f (m_k(x, y)))        (x, y ? K) f (x) = M \bigl(f (m_{1}(x, y)), \dots, f (m_{k}(x, y))\bigr) \qquad (x, y \in K) , (*)¶ where M is a k-variable operation on the image space Y, m₁,..., m_k are binary operations on X, K ì X K \subset X is closed under the operations m₁,..., m_k, and f : K ? Y f : K \rightarrow Y is considered as an unknown function.¶ The main result of this paper states that if the operations m₁,..., m_k, M satisfy certain commutativity relations and f satisfies (*) then there exists a unique extension of f to the (m₁,..., m_k)-affine hull K^* of K, such that (*) holds over K^*. (The set K^* is defined as the smallest subset of X that contains K and is (m₁,..., m_k)-affine, i.e., if x ? X x \in X , and there exists y ? K^* y \in K^* such that m₁(x, y), ?, m_k(x, y) ? K^* m_{1}(x, y), \ldots, m_{k}(x, y) \in K^* then x ? K^* x \in K^* ). As applications, extension theorems for functional equations on Abelian semigroups, convex sets, and symmetric convex sets are obtained.     

The character values of the irreducible constituents of a transitive permutation representation

In this article we determine the irreducible ordinary characters c_r \chi_r of a finite group G occurring in a transitive permutation representation (1_M )^G of a given subgroup M of G, and their multiplicities m_r = ((1_M)^G, c_r) 1 0 m_r = ((1_{M})^G, \chi_r) \neq 0 by means of a new explicit formula calculating the coefficients a_rk of the central idempotents e_r = ?_k=1^d a_rk D_k e_r = \sum\limits_{k=1}^{d} a_{rk} D_k in the intersection algebra B \cal B of (1_M )^G generated by the intersection matrices D_k corresponding to the double coset decomposition G = è_k=1^d Mx_k M G = \bigcup\limits_{k=1}^{d} Mx_{k} M .¶Furthermore, an explicit formula is given for the calculation of the character values c_r(x) \chi_{r}(x) of each element x ? G x \in G . Using this character formula we obtain a new practical algorithm for the calculation of a substantial part of the character table of G.     

A note on a conjecture of Borwein and Choi

A polynomial P(X) with coefficients {ǃ} of odd degree N - 1 is cyclotomic if and only if¶¶P(X) = ±F_p1 (±X)F_p2(±X^p1) ?F_pr(±X^{p1 p2 ?p_r-1}) P(X) = \pm \Phi_{p1} (\pm X)\Phi_{p2}(\pm X^{p1}) \cdots \Phi_{p_r}(\pm X^{p1 p2 \cdots p_r-1}) ¶where N = p₁ p₂ · · · p_r and the p_i are primes, not necessarily distinct, and where F_p(X) : = (X^p - 1) / (X - 1) \Phi_{p}(X) := (X^{p} - 1) / (X - 1) is the p-th cyclotomic polynomial. This is a conjecture of Borwein and Choi [1]. We prove this conjecture for a class of polynomials of degree N - 1 = 2^r p^l - 1 N - 1 = 2^{r} p^{\ell} - 1 for any odd prime p and for integers r, l\geqq 1 r, \ell \geqq 1 .     

Reducibility of polynomials a0(x) + a1 (x)y + a2 (x) y2 modulo p

Let f=a₀(x)+a₁(x)y+a₂(x)y² ? \Bbb Z[x,y]f=a_0(x)+a_1(x)y+a_2(x)y^2\in {\Bbb Z}[x,y] be an absolutely irreducible polynomial of degree m in x. We show that the reduction f mod p will also be absolutely irreducible if p 3 c_m·H(f)^e_mp\ge c_m\cdot H(f)^{e_m} where H (f) is the height of f and e₁ = 4,e₂ = 6, e₃ = 6 [2/3]{2}\over{3} and e_m = 2 m for m S 4. We also show that the exponents e_m are best possible for m 1 3m\ne 3 if a plausible number theoretic conjecture is true.     

Finding Large p-Colored Diameter Two Subgraphs

Given a coloring of the edges of the complete graph K on n vertices in k colors, a p-colored subgraph of K_n is any subgraph whose edges only use colors from some p element set. We show for k̿ and k\2hphk that there is always a p-colored diameter two subgraph of K_n containing at least [((k+p)n)/(2k)]\displaystyle{(k+p)n \over 2k} vertices and that this is best possible up to an additive constant l satisfying 0hl<k\2.     

On Ricci curvature of isotropic and Lagrangian submanifolds in complex space forms

Let M ⁿ be a Riemannian n-manifold. Denote by S(p) and [`(Ric)](p)\overline {Ric}(p) the Ricci tensor and the maximum Ricci curvature on M <sup>n</sup> at a point p ? M<sup>n</sup>p\in M^n, respectively. First we show that every isotropic submanifold of a complex space form [(M)\tilde]<sup>m</sup>(4 c)\widetilde M^m(4\,c) satisfies S ￡ ((n-1)c+ [(n<sup>2</sup>)/4] H<sup>2</sup>)gS\leq ((n-1)c+ {n^2 \over 4} H^2)g, where H<sup>2</sup> and g are the squared mean curvature function and the metric tensor on M <sup>n</sup>, respectively. The equality case of the above inequality holds identically if and only if either M <sup>n</sup> is totally geodesic submanifold or n = 2 and M <sup>n</sup> is a totally umbilical submanifold. Then we prove that if a Lagrangian submanifold of a complex space form [(M)\tilde]<sup>m</sup>(4 c)\widetilde M^m(4\,c) satisfies [`(Ric)] = (n-1)c+ [(n²)/4] H²\overline {Ric}= (n-1)c+ {n^2 \over 4} H^2 identically, then it is a minimal submanifold. Finally, we describe the geometry of Lagrangian submanifolds which satisfy the equality under the condition that the dimension of the kernel of second fundamental form is constant.     

Integral Lie powers of a lattice for the cyclic group of order 2

Let L_n denote the n-th homogeneous component of the free Lie ring L(W) on a given \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice W. This paper gives explicit formulae for the multiplicities of the three indecomposable \Bbb ZC₂{{\Bbb Z}}C_{2}-lattices in a Krull-Schmidt decomposition of L_n. In the case where W is a free \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice, L_n is shown to have no non-zero direct summand on which C₂ acts trivially - this extends a result of R. M. Bryant for the special case where W is the regular \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice. As an application, the structure of the higher dimensional modules associated to a non-cyclic free presentation of C₂ is determined.     

On formal quantum group laws

There exist natural generalizations of the concept of formal groups laws for noncommutative power series. This is a note on formal quantum group laws and quantum group law chunks. Formal quantum group laws correspond to noncommutative (topological) Hopf algebra structures on free associative power series algebras ká áx₁,...,x_m ? ?k\langle\! \langle x_1,\dots,x_m \rangle\! \rangle , k a field. Some formal quantum group laws occur as completions of noncommutative Hopf algebras (quantum groups). By truncating formal power series, one gets quantum group law chunks. ¶If the characteristic of k is 0, the category of (classical) formal group laws of given dimension m is equivalent to the category of m-dimensional Lie algebras. Given a formal group law or quantum group law (chunk), the corresponding Lie structure constants are determined by the coefficients of its chunk of degree 2. Among other results, a classification of all quantum group law chunks of degree 3 is given. There are many more classes of strictly isomorphic chunks of degree 3 than in the classical case.     

How Tight Is the Bollobás-Komlós Conjecture?

The bipartite case of the Bollobás and Komlós conjecture states that for every j₀, %>0 there is an !=!(j₀, %) >0 such that the following statement holds: If G is any graph with minimum degree at least n$\displaystyle {n \over 2}+%n then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶H)hj₀ \quad {\rm and} \quad b(H)h!n.$j (H)hj₀ \quad {\rm and} \quad b(H)h!n.¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v₁, …, v_n such that v_i~_Hv_j implies |imj|hb.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as %̂ then !̂. More precisely, we show that for any 0 such that that !(j₀, %)Д %.     

On a question of Erdös and Graham

We prove that for any $ \varepsilon > 0 $ \varepsilon > 0 there is k (e) k (\varepsilon) such that for any prime p and any integer c there exist k \leqq k(e) k \leqq k(\varepsilon) pairwise distinct integers x_i with 1 \leqq x_i \leqq p^e, i = 1, ?, k 1 \leqq x_{i} \leqq p^{\varepsilon}, i = 1, \ldots, k , and such that¶¶?_i=1^k [1/(x_i)] o c    (mod p). \sum\limits_{i=1}^k {{1}\over{x_i}} \equiv c\quad (\mathrm{mod}\, p). ¶¶ This gives a positive answer to a question of Erdös and Graham.     

A linear functional equation with a singularity at a fixed point

Summary. Local solutions of the functional equation¶¶z^k f( z) = ?_k=1ⁿG_k( z) f( s_kz ) +g( z) z{^\kappa} \phi \left( z\right) =\sum_{k=1}^nG_k\left( z\right) \phi \left( s_kz \right) +g\left( z\right) ¶with k > 0 \kappa > 0 and | s_k| \gt 1 \left| s_k\right| \gt 1 are considered. We prove that the equation is solvable if and only if a certain system of k \kappa conditions on G_k (k = 1, 2, ... , n) and g is fulfilled.     

White noise eliminates instability

Let x₁,..., x_n be points in the d-dimensional Euclidean space E^d with || x_i-x_j|| ￡ 1\| x_{i}-x_{j}\| \le 1 for all 1 \leqq i,j \leqq n1 \leqq i,j \leqq n, where || .||\| .\| denotes the Euclidean norm. We ask for the maximum M(d,n) of \mathop?_i, j=1ⁿ|| x_i-x_j|| ²\textstyle\mathop\sum\limits _{i,\,j=1}^{n}\| x_{i}-x_{j}\| ^{2} (see [4]). This paper deals with the case d = 2. We calculate M(2, n) and show that the value M(2, n) is attained if and only if the points are distributed as evenly as possible among the vertices of a regular triangle of edge-length 1. Moreover we give an upper bound for the value \mathop?_i, j=1ⁿ|| x_i-x_j|| \textstyle\mathop\sum\limits _{i,\,j=1}^{n}\| x_{i}-x_{j}\| , where the points x₁,...,x_n are chosen under the same constraints as above.     

L^p -uniqueness for Dirichlet operators with singular potentials

We study the problem of strong uniqueness in L^p for the Dirichlet operator perturbed by a singular complex-valued potential. First we construct the generator -H_p of a C₀-semigroup in L^p, with H_p extending the restriction of the perturbed Dirichlet operator to the set of smooth functions. The corresponding sesquilinear form in L² is not assumed to be sectorial. Then we reveal sufficient conditions on the logarithmic derivative # of the measure rdx \rho dx and the potential q which ensure that -H_p is the only extension of D+b·?-q \upharpoonright_C0^￥ \Delta +\beta \cdot \nabla -q \upharpoonright_{C_0^{\infty}} which generates a C₀-semigroup on L^p. The method of a priori estimates of solutions to corresponding differential equations is employed.     

On q-Olivier Functions

We consider words w₁· · · w_n with letters w_i ? {1, 2, 3, ?} w_i \in \{1, 2, 3, \ldots\} satisfying an up-up-down pattern like a₁ h a₂ h a₃ S a₄ h a₅ h a₆ S · · · . Attaching the (geometric) probability pq^i-1 to the letter i (with p = 1 -- q), every word gets a probability by assuming independence of letters. We are interested in the probability that a random word of length n satisfies the up-up-down condition. It turns out that one has to consider the 3 residue classes (mod 3) separately; then one can compute the associated probability generating function. They turn out to be q-analogues of so called Olivier functions.     

Smooth 2-homogeneous polynomials on Hilbert spaces

We determine the smooth points of the unit ball of the space of 2-homogeneous polynomials on a Hilbert space H. Working separately for the real and the complex cases we show that a smooth polynomial attains its norm. We deduce that the polynomial P is smooth if and only if there exists a unit vector x₀ in H such that P(x)=± á x,x₀ ñ ²+P₁(x₁)P(x)=\pm \left \langle x,x_{0}\right \rangle ^{2}+P_{1}(x_{1}) where x= á x,x₀ ñ x₀+x₁ x=\left \langle x,x_{0}\right \rangle x_{0}+x_{1} is the decomposition of x in H=span{ x₀} ?H₁H={\rm {span}}\{ x_{0}\} \oplus H_{1} and P₁ is a 2-homogeneous polynomial on H₁ of norm strictly less than 1.     

On the 3-Torsion Part of the Homology of the Chessboard Complex

Let 1 ≤ m ≤ n. We prove various results about the chessboard complex M _m,n , which is the simplicial complex of matchings in the complete bipartite graph K _m,n . First, we demonstrate that there is nonvanishing 3-torsion in [(H)\tilde]_d(\sf M_m,n; \mathbb Z){{\tilde{H}_d({\sf M}_{m,n}; {\mathbb Z})}} whenever \fracm+n-43 ￡ d ￡ m-4{{\frac{m+n-4}{3}\leq d \leq m-4}} and whenever 6 ≤ m < n and d = m − 3. Combining this result with theorems due to Friedman and Hanlon and to Shareshian and Wachs, we characterize all triples (m, n, d ) satisfying [(H)\tilde]_d (\sf M_m,n; \mathbb Z) 1 0{{\tilde{H}_d \left({\sf M}_{m,n}; {\mathbb Z}\right) \neq 0}}. Second, for each k ≥ 0, we show that there is a polynomial f _k (a, b) of degree 3k such that the dimension of [(H)\tilde]_k+a+2b-2 (\sf M_{k+a+3b-1,k+2a+3b-1}; \mathbb Z₃){{\tilde{H}_{k+a+2b-2}}\,\left({{\sf M}_{k+a+3b-1,k+2a+3b-1}}; \mathbb Z_{3}\right)}, viewed as a vector space over \mathbbZ₃{\mathbb{Z}_3}, is at most f _k (a, b) for all a ≥ 0 and b ≥ k + 2. Third, we give a computer-free proof that [(H)\tilde]₂ (\sf M_5,5; \mathbb Z) @ \mathbb Z₃{{\tilde{H}_2 ({\sf M}_{5,5}; \mathbb {Z})\cong \mathbb Z_{3}}}. Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M _m,n to the homology of M _m-2,n-1 and M _m-2,n-3.     

On the existence of certain measures appearing in distance geometry

Abstract. We prove the following result: Let X be a compact connected Hausdorff space and f be a continuous function on X x X. There exists some regular Borel probability measure m\mu on X such that the value of¶¶ ò\limit _X f(x,y)dm(y)\int\limit _X f(x,y)d\mu (y) is independent of the choice of x in X if and only if the following assertion holds: For each positive integer n and for all (not necessarily distinct) x₁,x₂,...,x_n,y₁,y₂,...,y_n in X, there exists an x in X such that¶¶ ?_i=1ⁿ f(x_i,x)=?_i=1ⁿ f(y_i,x).\sum\limits _{i=1}^n f(x_i,x)=\sum\limits _{i=1}^n f(y_i,x).     

A note on the complexity of the transportation problem with a permutable demand vector

In this note we investigate the computational complexity of the transportation problem with a permutable demand vector, TP-PD for short. In the TP-PD, the goal is to permute the elements of the given integer demand vector b=(b₁,…,b_n) in order to minimize the overall transportation costs. Meusel and Burkard [6] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values b_j, j=1,…,n, are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where b_j]{0,3} for j=1,…,n. As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if b_j] {0,1,2} holds for j=1,…,n. This result can be extended to the case where b_j]{3,3+1,3+2} for an integer 3.     

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).     

Independent Trees in Planar Graphs Independent trees

We prove the following statement: Let G be a finite k-connected undirected planar graph and s be a vertex of G. Then there exist k spanning trees T₁,…,T_k in G such that for each vertex xps of G, the k paths from x to s in T₁,…,T_k are pairwise openly disjoint.