Polytopes passing through circles

Suppose a convex body wants to pass through a circular hole in a wall. Does its ability to do so depend on the thickness of the wall? In fact in most cases it does, and in this paper we present a sufficient criterion for a polytope to allow an affirmative answer to the question.     

Birkhoff Completeness in Institutions

We develop an abstract proof calculus for logics whose sentences are ‘Horn sentences’ of the form: and prove an institutional generalization of Birkhoff completeness theorem. This result is then applied to the particular cases of Horn clauses logic, the ‘Horn fragment’ of preorder algebras, order-sorted algebras and partial algebras and their infinitary variants. the restriction of a logic to Horn sentences     

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     

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     

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     

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.     

B-splines with Birkhoff knots

A natural extension of the Curry-SchoenbergB-splines is given, which preserves such critical properties as variation diminishing and total positivity. Using this tool we give a characterization of the Birkhoff interpolation problem for spline functions.Communicated by Dietrich Braess.     

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     

The Magic Functions and Automorphisms of a Domain

We introduce the notion of magic functions of a general domain in and show that the set of magic functions of a given domain is an intrinsic complex-geometric object. We determine the set of magic functions of the symmetrised bidisc G and thereby find all automorphisms of G and a formula for the Carathéodory distance on G. Submitted: August 31, 2007. Accepted: November 11, 2007.     

On edge-antipodal <Emphasis Type="Italic">d</Emphasis>-polytopes

A convex d-polytope in ℝ ^d is called edge-antipodal if any two vertices that determine an edge of the polytope lie on distinct parallel supporting hyperplanes of the polytope. We introduce a program for investigating such polytopes, and examine those that are simple.      

Central Points of the Complete Quadrangle

Generalizing the classical geometry of the triangle in the Euclidean plane E, we define a central point of an n-gon as a symmetric function E ⁿ → E which commutes with all similarities. We first review various geometrical characterizations of some well-known central points of the quadrangle (n = 4) and show how a look at their mutual positions produces a morphologic classification (cyclic, trapezoidal, orthogonal etc.). From a basis of four central points, full information on the quadrangle can be retrieved. This generalizes a problem first faced by Euler for the triangle. Reconstructing a quadrangle from its central points is a geometric analogue of solving an algebraic equation of degree 4: here the diagonal triangle plays the role of a Lagrange resolvent and the determination of loci for the central points replaces the examination of discriminants for real roots.

---

Received: March 2007     

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.     

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,

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 the geometry of Nash equilibria and correlated equilibria

It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.We are grateful to Francoise Forges, Dan Arce, the editors, and several anonymous referees for helpful comments. This research was supported by the National Science Foundation under grant 98–09225 and by the Fuqua School of Business.The use of correlated mixed strategies in 2-player games was discussed by Raiffa (1951), who noted: it is a useful concept since it serves to convexify certain regions [of expected payoffs] in the Euclidean plane. (p. 8)Received: April 2002 / Revised: November 2003     

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.     

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.      

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.     

Transitive partial actions of groups

J. Kellendonk and M. V. Lawson established that each partial action of a group G on a set Y can be extended to a global action of G on a set Y _G containing a copy of Y. In this paper we classify transitive partial group actions. When G is a topological group acting on a topological space Y partially and transitively we give a condition for having a Hausdorff topology on Y _G such that the global group action of G on Y _G is continuous and the injection Y into Y _G is an open dense equivariant embedding.