On graphical partitions

An integer partition {₁,₂,..., _v } is said to be graphical if there exists a graph with degree sequence _i . We give some results corcerning the problem of deciding whether or not almost all partitions of even integer are non-graphical. We also give asymptotic estimates for the number of partitions with given rank.     

On graph planarity and semi-duality

In this (partly expository) paper we describe some of our recent results on graph planarity. These results concern strengthenings of Kuratowski's planarity criterion for quasi-4-connected graphs, for bipartite quasi-4-connected graphs, and for cubic bipartite graphs as well as generalizations of matroid duality of graphs and strengthenings of Whitney's planarity criterion.     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

On random partitions

Let S be a finite set with n labeled elements. One of the partitions of S is selected at random each of them has the same probability. Harper determined the expected number of subsets in the random partition. Haigh studied the probability that the random partition has (at least one) subset of a given size. The present paper considers the expected number of subsets in a given size. Average and maximum are also determined. Results are generalized for the case if the number of subsets in the partition is also fixed.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

On the planarity of Hanoi graphs

Hanoi graphs are the state graphs for Tower of Hanoi problems with three or more pegs. We prove hamiltonicity and present a complete analysis of planarity of these graphs.     

On core and bar-core partitions

If s and t are relatively prime integers, J.B. Olsson proved in (J. Comb. Theory, Ser. A 116:733–740, 2009) that the s-core of a t-core partition is again a t-core partition, and that the s-bar-core of a t-bar-core partition is again a t-bar-core partition. Here generalised results are proved for partitions and bar partitions when the restriction that s and t be relatively prime is removed.     

On the planarity of infinite 2-complexes

This paper is devoted to the problem of characterizing infinite planar polyhedra. We give two topological characterizations of planarity, and two others of proper planarity (embeddings with no accumulation points). We also give a combinatorial characterization of planarity, and proper planarity. In the case of compact polyhedra both results provide a weaker condition than that given by Gross and Rosen in [6].     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

On free fermions and plane partitions

We use free fermion methods to re-derive a result of Okounkov and Reshetikhin relating charged fermions to random plane partitions, and to extend it to relate neutral fermions to strict plane partitions.     

On zero-sum partitions and anti-magic trees

We study zero-sum partitions of subsets in abelian groups, and apply the results to the study of anti-magic trees. Extension to the nonabelian case is also given.     

On flushed partitions and concave compositions

In this work, we give combinatorial proofs for generating functions of two problems, i.e., flushed partitions and concave compositions of even length. We also give combinatorial interpretation of one problem posed by Sylvester involving flushed partitions and then prove it. For these purposes, we first describe an involution and use it to prove core identities. Using this involution with modifications, we prove several problems of different nature, including Andrews’ partition identities involving initial repetitions and partition theoretical interpretations of three mock theta functions of third order f(q), ?(q) and ψ(q). An identity of Ramanujan is proved combinatorially. Several new identities are also established.     

On the planarity of bicolored digraph grammar systems

D. Wood has asked in [2] whether there exists an inherently non-planar bicolored digraph-grammar language. We shall give below a negative answer to this question.     

On additive partitions of integers

Given a linear recurrence integer sequence U = {u_n}, u_n+2 = u_n+1 + u_r, n ? 1, u₁ = 1, u₂> u₁, we prove that the set of positive integers can be partitioned uniquely into two disjoint subsets such that the sum of any two distinct members from any one set can never be in U. We give a graph theoretic interpretation of this result, study related problems and discuss possible generalizations.     

On partitions with initial repetitions

We consider George Andrews’ fundamental theorem on partitions with initial repetitions and obtain some partition identities and parity results. A simplified, diagram-free, version of William Keith’s bijective proof of the theorem is presented. Lastly, we obtain extensions and variations of the theorem using a class of Rogers–Ramanujan-type identities for n-color partitions studied by A.K. Agarwal.     

On simplicial partitions of polytopes

Mathematical Notes - We prove some general properties of prismoids, i.e., polytopes all of whose vertices lie in two parallel planes. On the basis of these properties, we obtain a nontrivial lower...