On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Generalized projection and approximation of fixed points of nonself maps

Let K be a nonempty closed convex proper subset of a real uniformly convex and uniformly smooth Banach space E; T:K→E be an asymptotically weakly suppressive, asymptotically weakly contractive or asymptotically nonextensive map with F(T){xK: Tx=x}≠. Using the notion of generalized projection, iterative methods for approximating fixed points of T are studied. Convergence theorems with estimates of convergence rates are proved. Furthermore, the stability of the methods with respect to perturbations of the operators and with respect to perturbations of the constraint sets are also established.     

Reconstructible and Half-Reconstructible Tournaments: Application to Their Groups of Hemimorphisms

Let T and T¹ be tournaments with n elements, E a basis for T, E′ a basis for T′, and k ≥ 3 an integer. The dual of T is the tournament T” of basis E defined by T(x, y) = T(y, x) for all x, y ε E. A hemimorphism from T onto T′ is an isomorphism from T onto T” or onto T. A k-hemimorphism from T onto T′ is a bijection f from E to E′ such that for any subset X of E of order k the restrictions T/X and T¹/f(X) are hemimorphic. The set of hemimorphisms of T onto itself has group structure, this group is called the group of hemimorphisms of T. In this work, we study the restrictions to n – 2 elements of a tournament with n elements. In particular, we prove: Let k ≥ 3 be an integer, T a tournament with n elements, where n ≥ k + 5. Then the following statements are equivalent: (i) All restrictions of T to subsets with n – 2 elements are k-hemimorphic. (ii) All restrictions of T to subsets with n – 2 elements are 3-hemimorphic. (iii) All restrictions of T to subsets with n – 2 elements are hemimorphic. (iv) All restrictions of T to subsets with n – 2 elements are isomorphic, (v) Either T is a strict total order, or the group of hemimorphisms of T is 2-homogeneous.     

Semi-Topological K-Homology and Thomason''s Theorem

In this paper, we introduce the 'semi-topological K-homology' of complex varieties, a theory related to semi-topological K-theory much as connective topological K-homology is related to connective topological K-theory. Our main theorem is that the semi-topological K-homology of a smooth, quasi-projective complex variety Y coincides with the connective topological K-homology of the associated analytic space Y ^an. From this result, we deduce a pair of results relating semi-topological K-theory with connective topological K-theory. In particular, we prove that the 'Bott inverted' semi-topological K-theory of a smooth, projective complex variety X coincides with the topological K-theory of X ^an. In combination with a result of Friedlander and the author, this gives a new proof, in the special case of smooth, projective complex varieties, of Thomason's celebrated theorem that 'Bott inverted' algebraic K-theory with /n coefficients coincides with topological K-theory with /n coefficients.     

Exponent preserving subgroups of the finite simple groups

Given a group G denote with exp(G) its exponent, which is the least common multiple of the order of its elements. In this paper, we solve the problem of finding the finite simple groups having a proper subgroup with the same exponent. For each G with this property we will provide an explicit example of H<G with exp(G)?=?exp(H).     

Non-existence of KAM torus

Given an integrable Hamiltonian h ₀ with n-degrees of freedom and a Diophantine frequency ω, then, arbitrarily close to h ₀ in the C ^r topology with r < 2n, there exists an analytical Hamiltonian h _ε with no KAM torus of rotation vector ω. In contrast with it, KAM tori exist if perturbations are small in C ^r topology with r > 2n.     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

On Finite Saturated Chains of Overrings

If a domain R, with quotient field K, has a finite saturated chain of overrings from R to K, then the integral closure of R is a Prüfer domain. An integrally closed domain R with quotient field K has a finite saturated chain of overrings from R to K with length m ≥ 1 iff R is a Prüfer domain and |Spec(R)| =m + 1. In particular, we prove that a domain R has a finite saturated chain of overrings from R to K with length dim(R) iff R is a valuation domain and that an integrally closed domain R has a finite saturated chain of overrings from R to K with length dim (R) +1 iff R is a Prüfer domain with exactly two maximal ideals such that at most one of them fails to contain every non-maximal prime. The relationship with maximal non-valuation subrings is also established.     

Decomposing Hypergraphs into Simple Hypertrees

T be a simple k-uniform hypertree with t edges. It is shown that if H is any k-uniform hypergraph with n vertices and with minimum degree at least , and the number of edges of H is a multiple of t then H has a T-decomposition. This result is asymptotically best possible for all simple hypertrees with at least two edges. Received December 28, 1998     

Clifford algebra and the Lorentz transformation with (p, q) form

In this paper, the concepts of Lorentz inner product with (p, q) form, the Lorentz space and the Lorentz transformation with (p, q) form are given by using Clifford algebra. It is shown that L_m^p,q is the Lorentz transformation with (p, q) form, and the matrix equality relation of Minkowski space with (n − 1, 1) form is given. The examples are given to illustrate the corresponding results.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

Further properties of the Sumudu transform and its applications

This note discusses the general properties of the Sumudu transform and the Sumudu transform of special functions. For any function f (t) with corresponding Sumudu transform F (u), the effect of shifting the parameter t in f (t) by τ on the Sumudu transform F (u) is found. Also obtained are the effect of the multiplication of any function f (t) by a power of t and the division of the function f (t) by t on the Sumudu transform F (u). For any periodic function f (t) with periodicity T > 0 the Sumudu transform is easily derived. Illustrations are provided with Abel's integral equation, an integro-differential equation, a dynamic system with delayed time signals and a differential dynamic system.     

On character amenability of semigroup algebras

We study the character amenability of semigroup algebras. We work on general semigroups and certain semigroups such as inverse semigroups with a finite number of idempotents, inverse semigroups with uniformly locally finite idempotent set, Brandt and Rees semigroup and study the character amenability of the semigroup algebra l¹(S) in relation to the structures of the semigroup S. In particular, we show that for any semigroup S, if ?¹(S) is character amenable, then S is amenable and regular. We also show that the left character amenability of the semigroup algebra ?¹(S) on a Brandt semigroup S over a group G with index set J is equivalent to the amenability of G and J being finite. Finally, we show that for a Rees semigroup S with a zero over the group G, the left character amenability of ?¹(S) is equivalent to its amenability, this is in turn equivalent to G being amenable.     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

Another Approach to Topological Descent Theory

In the category T op of topological spaces and continuous functions, we prove that surjective maps which are descent morphisms with respect to the class E of continuous bijections are exactly the descent morphisms, providing a new characterization of the latter in terms of subfibrations E(X) of the basic fibration given by T op/X which are, essentially, complete lattices. Also effective descent morphisms are characterized in terms of effective morphisms with respect to continuous bijections. For classes E satisfying suitable conditions, we show that the class of effective descent morphisms coincides with the one of effective E-descent morphisms.     

Proximal Set-Open Topologies on Partial Maps

Let X, Y be T ₁ topological spaces. A partial map from X to Y is a continuous function f whose domain is a subspace D of X and whose codomain is Y. Let P(X, Y) be the set of partial maps with domains in a fixed class D. In analogy with the global case, we introduce on P(X, Y), whatever be the nature of the domain class D, new function space topologies, the proximal set-open topologies, briefly PSOTs, deriving from general networks on X and proximity on Y by replacing inclusion with strong inclusion. The PSOTs include the already known generalized compact-open topology on partial maps with closed domains. When domains are supposed closed, the network α closed and hereditarily closed and the proximity δ on Y Efremovic, then the PSOT attached to α and δ is uniformizable iff α is a Urysohn family in X. This revised version was published online in June 2006 with corrections to the Cover Date.