Fault Tolerance of Cayley Graphs

It is a difficult problem in general to decide whether a Cayley graph Cay(G; S) is connected where G is an arbitrary finite group and S a subset of G. For example, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. In this paper, it is shown that if a Cayley graph Cay(G; S) is known to be connected then its fault tolerance can be determined in polynomial time in |S|log(|G|). This is accomplished by establishing a new structural result for Cayley graphs. This result also yields a simple proof of optimal fault tolerance for an infinite class of Cayley graphs, namely exchange graphs. We also use the proof technique for our structural result to give a new proof of a known result on quasiminimal graphs. Received March 10, 2006     

Minors in Expanding Graphs

We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every -free graph G with average degree r ( are constants) contains a minor with average degree , for some constant ; (b) Every C_2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree , for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs. Received: March 2008, Accepted: May 2008     

Graphs of small dimensions

LetG=(V, E) be a graph withn vertices. The direct product dimension pdim (G) (c.f. [10], [12]) is the minimum numbert such thatG can be embedded into a product oft copies of complete graphsK _n.In [10], Lovász, Neetil and Pultr determined the direct product dimension of matchings and paths and gave sharp bounds for the product dimension of cycles, all logarithmic in the number of vertices.     

Preface: Old and New Perspectives on the Tutte Polynomial

This paper introduces a special issue on the Tutte polynomial derived from the Second Workshop on Tutte Polynomials and Applications, 2005, held at the Centre de Recerca Matemàtica, Bellaterra, Catalonia. We discuss the prehistory of Tutte polynomials and two current areas of research, to what extent a graph is determined by its chromatic or Tutte polynomial and generic versions of Tutte polynomials. Received February 28, 2007     

A 3-Local Characterization of M12 and SL3(3)

We identify the sporadic simple group M₁₂ and the simple group SL₃(3) from some part of their 3-local structure. We also present a graph theoretic analogue of our main theorem. Received: 6 October 2008, Revised: 25 October 2008     

A generalization of an integral of Ramanujan

This paper considers a generalization of an integral introduced by S. Ramanujan in his third notebook. Ramanujan’s integral is itself a version of the dilogarithm,

Stable bundles on 3-fold hypersurfaces

Using monads, we construct a large class of stable bundles of rank 2 and 3 on 3-fold hypersurfaces, and study the set of all possible Chern classes of stable vector bundles.     

Axiomatizing the Harsanyi solution,the symmetric egalitarian solution and the consistent solution for NTU-games

The validity of the axiomatization of the Harsanyi solution for NTU-games by Hart (1985) is shown to depend on the regularity conditions imposed on games. Following this observation, we propose two related axiomatic characterizations, one of the symmetric egalitarian solution (Kalai and Samet, 1985) and one of the consistent solution (Maschler and Owen, 1992). The three axiomatic results are studied, evaluated and compared in detail.Revised October 2004We thank an anonymous referee and an associate editor for their helpful comments. Geoffroy de Clippel also thanks Professors Sergiu Hart, Jean-François Mertens and Enrico Minelli. Horst Zank thanks the Dutch Science Foundation NWO and the British Council for support under the UK-Netherlands Partnership Programme in Science (PPS 706). The usual disclaimer applies.     

Collapsing monoids consisting of permutations and constants

In this paper we determine all collapsing transformation monoids that contain at least one unary constant operation and whose nonconstant operations are permutations. Furthermore, we find an infinite family of transformation monoids that consist of at least three unary constant operations and some permutations for which the corresponding monoidal intervals are 2-element chains. This research is supported by Hungarian National Foundation for Scientific Research grant nos. T 37877 and K 60148.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Left loops, bipartite graphs with parallelism and bipartite involution sets

We describe a representation of any semiregularleft loop by means of asemiregular bipartite involution set or, equivalently, a 1-factorization (i.e., a parallelism) of a bipartite graph, with at least one transitive vertex. In these correspondences,Bol loops are associated on one hand toinvariant regular bipartite involution sets and, on the other hand, totrapezium complete bipartite graphs with parallelism; K-loops (or Bruck loops) are further characterized by a sort of local Pascal configuration in the related graph. Research partially supported by the Research Project of M.I.U.R. (Italian Ministry of Education, University and Research) “Strutture geometriche, combinatoria e loro applicazioni” and by the Research group G.N.S.A.G.A. of INDAM.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

Packing Transitive Triples in a Tournament

We prove that a tournament with n vertices has more than arc-disjoint transitive triples, and more than arc-disjoint transitive quadruples, improving earlier bounds. In particular, 82 percent of the arcs of a tournament can be packed with transitive triples and 45 percent of the arcs of a tournament can be packed with transitive quadruples. Our proof is obtained by examining the fractional version of the problem and utilizing a connection between the integral and fractional versions. Received October 12, 2005     

Fillmore–Springer–Cnops Construction Implemented in <Literal><Emphasis FontCategory="SansSerif">GiNaC</Emphasis></Literal>

This is an implementation of the Fillmore–Springer–Cnops construction (FSCc) based on the Clifford algebra capacities [10] of the GiNaC computer algebra system. FSCc linearises the linear-fraction action of the M?bius group. This turns to be very useful in several theoretical and applied fields including engineering. The core of this realisation of FSCc is done for an arbitrary dimension, while a subclass for two dimensional cycles add some 2D-specific routines including a visualisation to PostScript files through the MetaPost or Asymptote software. This library is a backbone of many result published in [9], which serve as illustrations of its usage. It can be ported (with various level of required changes) to other CAS with Clifford algebras capabilities.     

Transferring strong boundedness among Laguerre orthogonal systems

Given the family of Laguerre polynomials, it is known that several orthonormal systems of Laguerre functions can be considered. In this paper we prove that an exhaustive knowledge of the boundedness in weighted L ^p of the heat and Poisson semigroups, Riesz transforms and g-functions associated to a particular Laguerre orthonormal system of functions, implies a complete knowledge of the boundedness of the corresponding operators on the other Laguerre orthonormal system of functions. As a byproduct, new weighted L ^p boundedness are obtained. The method also allows us to get new weighted estimates for operators related with Laguerre polynomials. Carlos Segovia passed away on April 3, 2007.     

A Construction of Subsets of the Reals which have a Similarity Decomposition

We construct a subset of the set R of real numbers of cardinality |R| which has a similarity decomposition, and which has an ordertype < that of R. Seymour Ginsburg had posed the question whether there exist sets with another ordertype than that of R which also have a similarity decomposition.      

On certain Mordell-Weil lattices of hyperelliptic type on rational surfaces

We study a class of rational hyperelliptic fibrations that can serve as a natural higher-genus analogue of rational elliptic fibrations from the standpoint of Mordell-Weil lattices. As a corollary, we obtain certain generalizations of the root lattices. We also describe the torsion part. Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 62, Algebraic Geometry-10, 1999.     

On totally reducible binary forms: I

Letv(n) be the number of positive numbers up to a large limit n that are expressible in essentially more than one way by a binary formf that is a product ofl > 2 distinct linear factors with integral coefficients. We prove that

Complements on surfaces

The main result is a boundedness theorem forn-complements on algebraic surfaces. In addition, this theorem is used in a classification of log Del Pezzo surfaces and birational contractions for threefolds. Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 62, Algebraic Geometry-10, 1999.     

On the birational rigidity of some pencils of Del Pezzo surfaces

In this note, we discuss birational properties of some three-dimensional Del Pezzo fibrations of degree two. Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 62, Algebraic Geometry-10, 1999.