Complete Minors In <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">s,s</Emphasis></Subscript>-Free Graphs

We prove that for a fixed integer s2 every K _s,s -free graph of average degree at least r contains a K _p minor where . A well-known conjecture on the existence of dense K _s,s -free graphs would imply that the value of the exponent is best possible. Our result implies Hadwigers conjecture for K _s,s -free graphs whose chromatic number is sufficiently large compared with s.     

Every Graph of Sufficiently Large Average Degree Contains a <Emphasis Type="Italic">C</Emphasis><Subscript>4</Subscript>-Free Subgraph of Large Average Degree

We prove that for every k there exists d=d(k) such that every graph of average degree at least d contains a subgraph of average degree at least k and girth at least six. This settles a special case of a conjecture of Thomassen.     

<Emphasis Type="Italic">A</Emphasis><Subscript>1</Subscript> weights and <Emphasis Type="Italic">d</Emphasis>-homogeneous measures on ahlfors <Emphasis Type="Italic">d</Emphasis>-regular space

Let X be an Ahlfors d-regular space and mad-regular measure on X . We prove that a measure μ on X is d-homogeneous if and only if μ is mutually absolutely continuous with respect to m and the derivative Dmμ(x) is an A1 weight. Also, we show by an example that every Ahlfors d-regular space carries a measure which is d-homogeneous but not d-regular.     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

On the b-Coloring of Cographs and <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Sparse Graphs

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ _b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every . We define a graph G to be b-monotonic if χ _b (H ₁) ≥ χ _b (H ₂) for every induced subgraph H ₁ of G, and every induced subgraph H ₂ of H ₁. In this work, we prove that P ₄-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. Flavia Bonomo: Partially supported by ANPCyT PICT-2007-00533 and PICT-2007-00518, and UBACyT Grants X069 and X606 (Argentina). Guillermo Durán: Partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina). Javier Marenco: Partially supported by ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina).     

Note making a <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free graph bipartite

We show that every K ₄-free graph G with n vertices can be made bipartite by deleting at most n ²/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3. This proves an old conjecture of P. Erdős. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Uniquely <Emphasis Type="Italic">C</Emphasis><Subscript>4</Subscript>-Saturated Graphs

For a fixed graph H, a graph G is uniquely H-saturated if G does not contain H, but the addition of any edge from [`(G)]{\overline{G}} to G completes exactly one copy of H. Using a combination of algebraic methods and counting arguments, we determine all the uniquely C ₄-saturated graphs; there are only ten of them.     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">1</Emphasis></Subscript> of a self-product of a curve

We present elements of H¹(C×C, ᵊ6₂) for certain specific curves C. The image of the element under the boundary map arising from the localization sequence of K-theory is the graph of frobenius endomorphism of the reduction of the curve modulo 3.     

On <Emphasis Type="Italic">s</Emphasis>-semipermutable subgroups of finite groups and <Emphasis Type="Italic">p</Emphasis>-nilpotency

A subgroup H of a group is said to be s-semipermutable in G if it is permutable with every Sylow p-subgroup of G with (p, |H|) = 1. Using the concept of s-semipermutable subgroups, some new characterizations of p-nilpotent groups are obtained and several results are generalized.     

Riesz <Emphasis Type="Italic">s</Emphasis>-Equilibrium Measures on <Emphasis Type="Italic">d</Emphasis>-Rectifiable Sets as <Emphasis Type="Italic">s</Emphasis> Approaches <Emphasis Type="Italic">d</Emphasis>

Let A be a compact set in of Hausdorff dimension d. For s ∈ (0,d) the Riesz s-equilibrium measure μ ^s is the unique Borel probability measure with support in A that minimizes

On products of <Emphasis Type="Italic">k</Emphasis> atoms

Let H be an atomic monoid. For let denote the set of all with the following property: There exist atoms (irreducible elements) u ₁, …, u _k , v ₁, …, v _m ∈ H with u ₁· … · u _k = v ₁ · … · v _m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets are almost arithmetical progressions. Suppose that H is a Krull monoid with finite cyclic class group G such that every class contains a prime (this includes the multiplicative monoids of rings of integers of algebraic number fields). We show that, for every , max which settles Problem 38 in [4]. Authors’ addresses: W. Gao, Center for Combinatorics, Nankai University, Tianjin 300071, P.R. China; A. Geroldinger, Institut für Mathematik und Wissenschaftliches Rechnen, Karl-Franzens-Universit?t Graz, Heinrichstra?e 36, 8010 Graz, Austria     

Realizability of the <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript>-distance functions by homology classes of path spaces

In previous papers, we have constructed and studied mappings d _k : M × M → ℝ called the H _k -distance functions. The main result of this paper is a theorem on realizability of the generalized distances d _k (υ, w), υ, w ∈ M, by critical values of the length functional L: Ω(M, υ, w) → ℝ generated by nontrivial homology classes of the space Ω(M, υ, w) of paths joining the points υ and w.     

High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

On Generalized Hardy Sums <Emphasis Type="Italic">s</Emphasis><Subscript>5</Subscript>(<Emphasis Type="Italic">h,k</Emphasis>)

The aim of this paper is to study generalized Hardy sums s ₅(h, k). By using mediants and the adjacent difference of Farey fractions, we establish a relationship between s ₅(h, k) and Farey fractions. Using generalized Dedekind sums and a generalized periodic Bernoulli function, we define generalized Hardy sums s _5,p (h,k). A relationship between s _5,p (h, k) and the Hurwitz zeta function is established. By using the definitions of Lambert series and cotπz, we establish a relationship between s ₅(h,k) and Lambert series.__________Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 10, pp. 1434–1440, October, 2004.     

<Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free subgraphs of random graphs revisited

In Combinatorica 17(2), 1997, Kohayakawa, ?uczak and Rödl state a conjecture which has several implications for random graphs. If the conjecture is true, then, for example, an application of a version of Szemerédi’s regularity lemma for sparse graphs yields an estimation of the maximal number of edges in an H-free subgraph of a random graph G _{n, p} . In fact, the conjecture may be seen as a probabilistic embedding lemma for partitions guaranteed by a version of Szemerédi’s regularity lemma for sparse graphs. In this paper we verify the conjecture for H = K ₄, thereby providing a conceptually simple proof for the main result in the paper cited above.     

Best approximation by ridge functions in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-spaces

We study the approximation of the classes of functions by the manifold R _n formed by all possible linear combinations of n ridge functions of the form r(a · x)): It is proved that, for any 1 ≤ q ≤ p ≤ ∞, the deviation of the Sobolev class W ^r _p from the set R _n of ridge functions in the space L _q (B ^d ) satisfies the sharp order n ^-r/(d-1).     

Nonlinear Preserver Problems on B（H）

Let H be a complex Hilbert space of dimension greater than 2, and B(H) denote the Banach algebra of all bounded linear operators on H. For A, B ∈ B(H), define the binary relation A ≤* B by A*A = A*B and AA* = AB*. Then (B(H), “≤*”) is a partially ordered set and the relation “≤*” is called the star order on B(H). Denote by Bs(H) the set of all self-adjoint operators in B(H). In this paper, we first characterize nonlinear continuous bijective maps on B _s (H) which preserve the star order in both directions. We characterize also additive maps (or linear maps) on B(H) (or nest algebras) which are multiplicative at some invertible operator.     

On Transference of Multipliers on Matrix Weighted <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-Spaces

We consider a periodic matrix weight W defined on ℝ ^d and taking values in the N×N positive-definite matrices. For such weights, we prove transference results between multiplier operators on L _p (ℝ ^d ;W) and L_p(\mathbb T^d;W)L_{p}(\mathbb {T}^{d};W), 1<p<∞, respectively. As a specific application, we study transference results for homogeneous multipliers of degree zero.     

On the Theory of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>)-Banach Lattices

Given 1≤ p,q < ∞, let BL_pL_q be the class of all Banach lattices X such that X is isometrically lattice isomorphic to a band in some L_p(L_q)-Banach lattice. We show that the range of a positive contractive projection on any BL_pL_q-Banach lattice is itself in BL_pL_q. It is a consequence of this theorem and previous results that BL_pL_q is first-order axiomatizable in the language of Banach lattices. By studying the pavings of arbitrary BL_pL_q-Banach lattices by finite dimensional sublattices that are themselves in this class, we give an explicit set of axioms for BL_pL_q. We also consider the class of all sublattices of L_p(L_q)-Banach lattices; for this class (when p/q is not an integer) we give a set of axioms that are similar to Krivine’s well-known axioms for the subspaces of L_p-Banach spaces (when p/2 is not an integer). We also extend this result to the limiting case q = ∞.     

Goal-minimally <Emphasis Type="Italic">k</Emphasis>-elongated graphs

Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d _G−uv (x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages. This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09.