Distance-Balanced Graphs

Distance-balanced graphs are introduced as graphs in which every edge uv has the following property The number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Basic properties of these graphs are obtained. The new concept is connected with symmetry conditions in graphs and local operations on graphs are studied with respect to it. Distance-balanced Cartesian and lexicographic products of graphs are also characterized. Several open problems are posed along the way. Received August 31, 2005     

A Cayley theorem for distributive lattices

A Cayley-like representation theorem for distributive lattices is proved. Support of the research of the first author by the Czech Government Research Project MSM 6198959214 is gratefully acknowledged.     

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.     

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     

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.     

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.     

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.      

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.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.     

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.     

Bounds on leaves of one-dimensional foliations

Let X be a variety over an algebraically closed field, a onedimensional singular foliation, and a projective leaf of . We prove that

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.     

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.      

Simple random order methods to share costs

A simple random order method (SROM) is an extension of Webers random order values (ROVs), which allows the convex weights on orderings of agents to depend on the set of agents with strictly positive demands. Thus, a SROM permits different coalitions of agents adopting exogenously different ROVs to take into account the differences in, for example, bargaining abilities, rights or status of the agents in a cost sharing problem. Within the family of additive methods satisfying the dummy axiom, we characterize SROMs by Measurement Invariance in the discrete cost sharing model where demands are indivisible, and Ordinality in the continuous model where demands are divisible, respectively.I am indebted to Yves Sprumont for initiating and providing the starting point of this paper, and for his great help in this work. I thank Hervé Moulin, Ahmet Alkan, Anirban Kar, an associate editor, and a referee whose comments greatly improved the paper. I gratefully acknowledge the support from Sabanci University Research Fund.     

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

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     

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.