Search

Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n) = 1 and t(n) = n!. For n odd, we prove (nφ(n))/2k ≤ s(n) ≤ n!·2-(n-1)/2/((n-1)/2)! and 2(n-1)/2·(n-1/2)! ≤ t(n) ≤ 2k · (n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function. [ABSTRACT FROM AUTHOR]

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic. [ABSTRACT FROM AUTHOR]

We consider a general concept of composition and decomposition of objects, and discuss a few natural properties one may expect from a reasonable choice thereof. It will be demonstrated how this leads to multiplication and co-multiplication laws, thereby providing a generic scheme furnishing combinatorial classes with an algebraic structure. The paper is meant as a gentle introduction to the concepts of composition and decomposition with the emphasis on combinatorial origin of the ensuing algebraic constructions. [ABSTRACT FROM AUTHOR]

A decomposable combinatorial structure consists of simpler objects called components which by themselves can not be further decomposed. We focus on the multi-set construction where the component generating function C(z) is of alg-log type, that is, C(z) behaves like c + d(1 - z/ρ)α (ln 1 / 1 - z/ρ)β (1 + o(1)) when z is near the dominant singularity ρ. We provide asymptotic results about the size of the smallest components in random combinatorial structures for the cases 0 < α < 1 and any β and α < 0 and β = 0. The particular case α = 0 and β = 1, the so-called exp-log class, has been treated in previous papers. We also provide similar asymptotic estimates for combinatorial objects with a restricted pattern, that is, when part of its factorization pattern is known. We extend our results to include certain type of integers partitions. [ABSTRACT FROM AUTHOR]

In this paper we discuss the bounds of and relations among various kinds of intersection numbers of graphs. Especially, we address extremal graphs with respect to the established bounds. The uniqueness of the minimum-size intersection representations for some graphs is also studied. In the course of this work, we introduce a superclass of chordal graphs, defined in terms of a generalization of simplicial vertex and perfect elimination ordering. Keywords: chordal graph, diamond-free elimination graph, edge clique graph, fractional intersection number, Helly property, intersection graph, intersection number, purple graph, maximal clique, maximal clique irreducible graph, ST weighting algorithm, unique representability. [ABSTRACT FROM AUTHOR]

The following problem was solved by Woodall in 1972: for any pair of nonnegative integers n and k < n/2 - 1 find the minimum integer g(n, k) such that every graph with n vertices and at least g(n, k) edges contains a cycle of length n - k. Woodall proved even more: the size g(n, k), in fact, guarantees the existence of cycles Cp for all 3 ≤ p ≤ n - k. In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n; m ≤ n; and size greater than n(m - k - 1) + k + 1 contains a cycle of length 2m - 2k, where m ≥ 1/2k² + 3/2k + 4; k ∈ ℕ. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m - 2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m ≥ 2k + 2. [ABSTRACT FROM AUTHOR]

We consider the sum u of differences between adjacent letters of a word of n letters, chosen uniformly at random from a given alphabet. This paper obtains the enumerating generating function for the number of such words with respect to the sum u, as well as explicit formulas for the mean and variance of u. [ABSTRACT FROM AUTHOR]

A k-uniform hypergraph H = (V;E) is said to be self-complementary whenever it is isomorphic with its complement H̅ = (V; (kV) - E). Every permutation σ of the set V such that σ(e) is an edge of H̅ if and only if e ∈ E is called self-complementing. 2-self-comlementary hypergraphs are exactly self complementary graphs introduced independently by Ringel (1963) and Sachs (1962). For any positive integer n we denote by λ(n) the unique integer such that n = 2λ(n) c, where c is odd. In the paper we prove that a permutation σ of [1; n] with orbits O1,..., Om is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l ≥ 0 such that k = a2l + s, a is odd, 0 ≤ s < 2l and the following two conditions hold: (i) n = b2l+1 + r, r ∈ {0,...,2l - 1 + s}, and (ii) ∑i:λ(|Oi|)≤l|Oi|≤ r. For k = 2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the recognition problem on three classes of perfect graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min{m α(n, n), m + n log n}) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min{m α (n, n), m + n log n})-time and O(n + m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement G of the graph G is HH-free can be efficiently resolved in O(nm) time using O(n²) space, which leads to an O(nm)-time and O(n²) space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n³) time and O(n²) space. [ABSTRACT FROM AUTHOR]

Recently, Green and Losonczy [5, 6] introduced freely braided permutations as a special class of restricted permutations that has arisen in the study of Schubert varieties. They suggest as an open problem to enumerate the number of freely braided permutations in Sn. In this paper, we prove that the generating function for the number of freely braided permutations in Sn is given by 1-3x-2x²+(1+x)√p1-4x/1-4x-x²+(1-x²)√1-4x. [ABSTRACT FROM AUTHOR]