Vertex partitions of r -edge-colored graphs

Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G. In the authors’ previous work, it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P = NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path (cycle) partition problem. Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given. Supported by the National Natural Science Foundation of China, PCSIRT and the “973” Program.     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

Neighborly polytopes

A 2m-polytopeQ isneighborly if eachm vertices ofQ determine a face. It is shown that the combinatorial structure of a neighborly 2m-polytope determines the combinatorial structure of every subpolytope. We develop a construction of “sewing a vertex onto a polytope”, which, when applied to a neighborly 2m-polytope, yields a neighborly 2m-polytope with one more, vertex. Using this construction, we show that the numberg(2m+β,2m) of combinatorial types of neighborly 2m-polytopes with 2m+β vertices grows superexponentially as β→∞ (m≧2 fixed) and asm→∞ (β≧4 fixed).     

Extremal Problems For Transversals In Graphs With Bounded Degree

We introduce and discuss generalizations of the problem of independent transversals. Given a graph property , we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property . In this paper we study this problem for the following properties : “acyclic”, “H-free”, and “having connected components of order at most r”. We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations on the power of this topological method. We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such that every transversal contains a fixed graph H as a subgraph. Finally, we pose several open questions. * Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich. † Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826.     

Maximum Orbit Weights in the σ-game and Lit-only σ-game on Grids and Graphs

Let G be a graph in which each vertex can be in one of two states: on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ⁺-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes, to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better. The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only versions of both games.     

Neighborly combinatorial 3-manifolds with dihedral automorphism group

It is well known that for anyn≧5 the boundary complex of the cyclic 4-polytopeC(n, 4) is a neighborly combinatorial 3-sphere admitting a vertex transitive action of the dihedral groupD _n of order 2n. In this paper we present a similar series of neighborly combinatorial 3-manifolds withn≧9 vertices, each homeomorphic to the “3-dimensional Klein bottle”. Forn=9 andn=10 these examples have been observed. before by A. Altshuler and L. Steinberg. Moreover we give a computer-aided enumeration of all neighborly combinatorial 3-manifolds with such a symmetry and with at most 19 vertices. It turns out that there are only four other types, one with 10, 15, 17, 19 vertices. We also discuss the more general case of manifolds with cyclic automorphism groupC _n.     

Structure of <Emphasis Type="Italic">K</Emphasis>-interval exchange transformations: Induction,trajectories, and distance theorems

We define a new induction algorithm for k-interval exchange transformations associated to the “symmetric” permutation i ↦ k − i + 1. Acting as a multi-dimensional continued fraction algorithm, it defines a sequence of generalized partial quotients given by an infinite path in a graph whose vertices, or states, are certain trees we call trees of relations. This induction is self-dual for the duality between the usual Rauzy induction and the da Rocha induction. We use it to describe those words obtained by coding orbits of points under a symmetric interval exchange, in terms of the generalized partial quotients associated with the vector of lengths of the k intervals. As a consequence, we improve a bound of Boshernitzan in a generalization of the three-distances theorem for rotations. However, a variant of our algorithm, applied to a class of interval exchange transformations with a different permutation, shows that the former bound is optimal outside the hyperelliptic class of permutations.     

Zonotopes with Large 2D-Cuts

There are d-dimensional zonotopes with n zones for which a 2-dimensional central section has Ω(n ^d−1) vertices. For d=3, this was known, with examples provided by the “Ukrainian easter eggs” by Eppstein et al. Our result is asymptotically optimal for all fixed d≥2.     

Algebraic connectivity and degree sequences of trees

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector.     

A rigidity theorem for automorphism groups of trees

A group G is called unsplittable if Hom(G, ℤ) = 0 and this group is not a non-trivial amalgam. Let X be a tree with a countable number of edges incident at each vertex and G be its automorphism group. In this paper we prove that the vertex stabilizers are unsplittable groups. Bass and Lubotzky proved (see [3]) that for certain locally finite trees X, the automorphism group determines the tree X (that is, knowing the automorphism group we can “construct” the tree X). We generalize this Theorem of Bass and Lubotzky, using the above result. In particular we show that the Theorem holds even for trees which are not locally finite. Moreover, we prove that the permutation group of an infinite countable set is unsplittable and the infinite (or finite) cartesian product of unsplittable groups is an unsplittable group as well. This research was supported by the European Social Fund and National resources-EPEAEK II grant Pythagoras 70/3/7298.     

On the Crossing Numbers of Products of Stars and Graphs of Order Five

 There are several known exact results on the crossing numbers of Cartesian products of paths or cycles with “small” graphs. In this paper we extend these results to the Cartesian products of two specific 5-vertex graphs with the star K _{1, n} . In addition, we give the crossing number of the graph obtained by adding two edges to the graph K _{1,4, n} in such a way that these new edges join a vertex of degree n+1 of the graph K _{1,4, n} with two its vertices of the same degree. Received: December 8, 1997 Final version received: August 14, 1998     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

Cantor set and interpolation

In 1998, Y. Benyamini published interesting results concerning interpolation of sequences using continuous functions ℝ → ℝ. In particular, he proved that there exists a continuous function ℝ → ℝ which in some sense “interpolates” all sequences (x _n ) _n∈ℤ ∈ [0, 1]^ℤ “simultaneously.” In 2005, M.R. Naulin and C. Uzcátegui unified and generalized Benyamini’s results. In this paper, the case of topological spaces X and Y with an Abelian group acting on X is considered. A similar problem of “simultaneous interpolation” of all “generalized sequences” using continuous mappings X → Y is posed. Further generalizations of Naulin-Uncátegui theorems, in particular, multidimensional analogues of Benyamini’s results are obtained.     

Compactness for a class of hit-and-miss hyperspaces

In the study of some kind of generalized Vietoris-type topologies for the hyperspace of all nonempty closed subsets of a topological space (X, τ), namely the so called Δ-hit-and-miss-topologies with Δ⊇Cl(X) (or Δ-topologies), which was initiated by the second author in 1965, it is obvious, that the non-compactness of such a hyperspace often depends on the non-compactness even in the lower-semifinite topology (induced by the “hit-sets”), which is contained in all hypertopologies of this type. Otherwise, compactness for these topologies is easily obtained from the compactness of (X, τ) by well-known theorems, if the “miss-sets” are induced either by compact or closed subsets. To obtain a similar result for topologies with “miss-sets” generated by subsets with a property which generalizes both, closedness and compactness especially in the non-Hausdorff case, we use consequently a quite set-theoretical lemma, stated at the beginning.     

Enumeration of Unrooted Odd-Valent Regular Planar Maps

We derive closed formulae for the numbers of rooted maps with a fixed number of vertices of the same odd degree except for the root vertex and one other exceptional vertex of degree 1. The same applies to the generating functions for these numbers. Similar results, but without the vertex of degree 1, were obtained by the first author and Rahman. We also show, by manipulating a recursion of Bouttier, Di Francesco and Guitter, that there are closed formulae when the exceptional vertex has arbitrary degree. We combine these formulae with results of the second author to count unrooted regular maps of odd degree. In this way we obtain, for each even n, a closed formula for the function f _n whose value at odd positive integers r is the number of unrooted maps (up to orientation-preserving homeomorphisms) with n vertices and degree r. The formula for f _n becomes more cumbersome as n increases, but for n > 2 each has a bounded number of terms independent of r.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Generalized cluster complexes via quiver representations

We give a quiver representation theoretic interpretation of generalized cluster complexes defined by Fomin and Reading. Using d-cluster categories defined by Keller as triangulated orbit categories of (bounded) derived categories of representations of valued quivers, we define a d-compatibility degree (−∥−) on any pair of “colored” almost positive real Schur roots which generalizes previous definitions on the noncolored case and call two such roots compatible, provided that their d-compatibility degree is zero. Associated to the root system Φ corresponding to the valued quiver, using this compatibility relation, we define a simplicial complex which has colored almost positive real Schur roots as vertices and d-compatible subsets as simplices. If the valued quiver is an alternating quiver of a Dynkin diagram, then this complex is the generalized cluster complex defined by Fomin and Reading. Supported by the NSF of China (Grants 10471071) and by the Leverhulme Trust through the network ‘Algebras, Representations and Applications’.     

An Isoperimetric Theorem in Plane Geometry

Abstract. Let P be a simple polygon. Let the vertices of P be mapped, according to a counterclockwise traversal of the boundary, into a strictly increasing sequence of real numbers in [0, 2π) . Let a ray be drawn from each vertex so that the angle formed by the ray and a horizontal line pointing to the right equals, in measure, the number mapped to the vertex. Whenever the rays from two consecutive vertices intersect, let them induce the triangular region with extreme points comprising the vertices and the intersection point. It is shown that there is a fixed α such that if all of the assigned angles are increased by α , the triangular regions induced by the redirected rays cover the interior of P . This covering implies the standard isoperimetric inequalities in two dimensions, as well as several new inequalities, and resolves a question posed by Yaglom and Boltanskii.     

Each 3-strong Tournament Contains 3 Vertices Whose Out-arcs Are Pancyclic

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it is in a cycle of length k for all 3 ≤ k ≤ n. Yeo (Journal of Graph Theory, 50 (2005), 212–219) proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong tournaments. The author is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH Aachen University, Germany.