Independent Trees and Branchings in Planar Multigraphs

 The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T ₁, … ,T _k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T ₁, … ,T _k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open. Received: January 30, 1995 / Revised: October 7, 1996     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

The 2-Pebbling Property and a Conjecture of Graham's

The pebbling number of a graph G, f(G), is the least m such that, however m pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. It is conjectured that for all graphs G and H, f(G 2H)hf(G)f(H).¶Let C_m and C_n be cycles. We prove that f(C_m 2C_n)hf(C_m) f(C_n) for all but a finite number of possible cases. We also prove that f(G2T)hf(G) f(T) when G has the 2-pebbling property and T is any tree.     

Independent trees in graphs

IfG is a finite undirected graph ands is a vertex ofG, then two spanning treesT ₁ andT ₂ inG are calleds — independent if for each vertexx inG the paths fromx tos inT ₁ andT ₂ are openly disjoint. It is known that the following statement is true fork3: IfG isk-connected, then there arek pairwises — independent spanning, trees inG. As a main result we show that this statement is also true fork=4 if we restrict ourselves to planar graphs. Moreover we consider similar statements for weaklys — independent spanning trees (i.e., the tree paths from a vertex tos are edge disjoint) and for directed graphs.     

Odd order groups with the rewriting property Q3

Let n be an integer greater than 1, and let G be a group. A subset {x₁, x₂, ..., x_n} of n elements of G is said to be rewritable if there are distinct permutations p \pi and s \sigma of {1, 2, ..., n} such that¶¶x_p(1)x_p(2) ?x_p(n) = x_s(1)x_s(2) ?x_s(n). x_{\pi(1)}x_{\pi(2)} \ldots x_{\pi(n)} = x_{\sigma(1)}x_{\sigma(2)} \ldots x_{\sigma(n)}. ¶¶A group is said to have the rewriting property Q_n if every subset of n elements of the group is rewritable. In this paper we prove that a finite group of odd order has the property Q₃ if and only if its derived subgroup has order not exceeding 5.     

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₀, %)Д %.     

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.     

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.     

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.     

Auto-equivalences of derived categories acting on cohomology

Let A be a k-algebra which is projective as a k-module, let M be an A-module whose endomorphisms are given by multiplication by central elements of A, and let TrPic_k(A) be the group of standard self-equivalences of the derived category of bounded complexes of A-modules. Then we define an action of the stabilizer of M in TrPic_k(A) on the Ext-algebra of M. In case M is the trivial module for the group algebra kG = A, this defines an action on the cohomology ring of G which extends the well-known action of the automorphism group of G on the cohomology group.     

The Theorem of the k-1 Happy Divorces

Given a binary relation R between the elements of two sets X and Y and a natural number k, it is shown that there exist k injective maps f₁, f₂,...,f_k: X \hookrightarrow Y X \hookrightarrow Y with # {f₁(x), f₂(x),...,f_k(x)}=k    and    (x,f₁(x)), (x, f₂(x)),...,(x, f_k(x)) ? R \# \{f_1(x), f_2(x),...,f_k(x)\}=k \quad{\rm and}\quad (x,f_1(x)), (x, f_2(x)),...,(x, f_k(x)) \in R for all x ? X x \in X if and only if the inequality k ·# A ￡ ?_{y ? Y} min(k, #{a ? A | (a,y) ? R}) k \cdot \# A \leq \sum_{y \in Y} min(k, \#\{a \in A \mid (a,y) \in R\}) holds for every finite subset A of X, provided {y ? Y | (x,y) ? R} \{y \in Y \mid (x,y) \in R\} is finite for all x ? X x \in X .¶Clearly, as suggested by this paper's title, this implies that, in the context of the celebrated Marriage Theorem, the elements x in X can (simultaneously) marry, get divorced, and remarry again a partner from their favourite list as recorded by R, for altogether k times whenever (a) the list of favoured partners is finite for every x ? X x \in X and (b) the above inequalities all hold.¶In the course of the argument, a straightforward common generalization of Bernstein's Theorem and the Marriage Theorem will also be presented while applications regarding (i) bases in infinite dimensional vector spaces and (ii) incidence relations in finite geometry (inspired by Conway's double sum proof of the de Bruijn-Erdös Theorem) will conclude the paper.     

Finite groups in which normality is a transitive relation

Let G be a finite group. We say that G is a T₀-group, if its Frattini quotient group G/F(G)G/\Phi (G) is a T-group, where by a T-group we mean a group in which every subnormal subgroup is normal. We determine the structure of a non T₀-group G all of whose proper subgroups are T₀-groups.     

Wilson's functional equation on P3-groups

Summary. Consider Wilson's functional equation¶¶f(xy) + f(xy^-1) = 2f(f)g(y) f(xy) + f(xy^{-1}) = 2f(f)g(y) , for f,g : G ? K f,g : G \to K ¶where G is a group and K a field with char K 1 2 {\rm char}\, K\ne 2 .¶Aczél, Chung and Ng in 1989 have solved Wilson's equation, assuming that the function g satisfies Kannappan's condition g(xyz) = g(xzy) and f(xy) = f(yx) for all x,y,z ? G x,y,z\in G .¶In the present paper we obtain the general solution of Wilson's equation when G is a P₃-group and we show that there exist solutions different of those obtained by Aczél, Chung and Ng.¶A group G is said to be a P₃-group if the commutator subgroup G' of G, generated by all commutators [x,y] := x^-1y^-1xy, has the order one or two.     

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.     

Solution of generalized bisymmetry type equations without surjectivity assumptions

Summary. The solution of the rectangular m ×n m \times n generalized bisymmetry equation¶¶F(G₁(x₁₁,...,x_1n),..., G_m(x_m1,...,x_mn))     =     G(F₁(x₁₁,..., x_m1),...,  F_n(x_1n,...,x_mn) ) F\bigl(G_1(x_{11},\dots,x_{1n}),\dots,\ G_m(x_{m1},\dots,x_{mn})\bigr) \quad = \quad G\bigl(F_1(x_{11},\dots, x_{m1}),\dots, \ F_n(x_{1n},\dots,x_{mn}) \bigr) (A)¶is presented assuming that the functions F, G_j, G and F_i (j = 1, ... , m , i = 1, ... , n , m S 2, n S 2) are real valued and defined on the Cartesian product of real intervals, and they are continuous and strictly monotonic in each real variable. Equation (A) is reduced to some special bisymmetry type equations by using induction methods. No surjectivity assumptions are made.     

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).     

The determination of the thermal properties of a heat conductor in a nonlinear heat conduction problem

This paper considers the inverse determination of the positive unknown thermal properties K(T), C(T) and the unknown temperature T(_{x, t}) in the nonlinear transient heat conduction equation. In addition to prescribed initial and/or boundary values, specified continuously differentiable temperature data T(x₀, t) with non-zero derivative at a single sensor location x = x₀ is given. When K(T) and C(T) obey a certain relationship which enables one to linearise exactly the nonlinear heat equation then their dependence upon T is obtained explicitly, whilst the unknown temperature T(x, t) is obtained implicitly and is then calculated numerically. Results are presented and discussed for infinite, semi-infinite and finite slabs.     

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 strong convergence theorem for asymptotically nonexpansive mappings in Banach spaces

Let C be a closed, convex subset of a uniformly convex Banach space whose norm is uniformly Gâteaux differentiable and let T be an asymptotically nonexpansive mapping from C into itself such that the set F (T) of fixed points of T is nonempty. Let {a_n} be a sequence of real numbers with 0 ￡ a_n ￡ 10 \leq a_n \leq 1, and let x and x₀ be elements of C. In this paper, we study the convergence of the sequence {x_n} defined by¶¶x_n+1=a_n x + (1-a_n) [1/(n+1)] ?_j=0ⁿ T^j x_n   x_{n+1}=a_n x + (1-a_n) {1\over n+1} \sum\limits_{j=0}^n T^j x_n\quad for n=0,1,2,...  . n=0,1,2,\dots \,.     

On matrix near-rings

Let R be a right near-ring with identity and M_n(R) be the near-ring of n 2 n matrices over R in the sense of Meldrum and Van der Walt. In this paper, M_n(R) is said to be s\sigma-generated if every n 2 n matrix A over R can be expressed as a sum of elements of X_n(R), where X_n(R)={f_ij^r | 1\leqq i, j\leqq n, r ? R}X_n(R)=\{f_{ij}^r\,|\,1\leqq i, j\leqq n, r\in R\}, is the generating set of M_n(R). We say that R is s\sigma-generated if M_n(R) is s\sigma-generated for every natural number n. The class of s\sigma-generated near-rings contains distributively generated and abstract affine near-rings. It is shown that this class admits homomorphic images. For abelian near-rings R, we prove that the zerosymmetric part of R is a ring, so the class of zerosymmetric abelian s\sigma-generated near-rings coincides with the class of rings. Further, for every n, there is a bijection between the two-sided subgroups of R and those of M_n(R).