On generalized Kneser hypergraph colorings

In 2002, the second author presented a lower bound for the chromatic numbers of hypergraphs , “generalized r-uniform Kneser hypergraphs with intersection multiplicities s.” It generalized previous lower bounds by K?í? (1992/2000) for the case s=(1,…,1) without intersection multiplicities, and by Sarkaria (1990) for . Here we discuss subtleties and difficulties that arise for intersection multiplicities si>1:

(1)

In the presence of intersection multiplicities, there are two different versions of a “Kneser hypergraph,” depending on whether one admits hypergraph edges that are multisets rather than sets. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version.

(2)

The reductions to the case of prime r in the proofs by Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of r. Currently we have no valid proof for the lower bound result in the other cases.

We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.     

The Johnson graph J(d,r) is unique if (d,r) ≠ (2, 8)

We use the classical Root Systems to show the Johnson graph J(d, r) (2 ⩽ 2d ⩽ r < ∞) is the unique distance-regular graph with its intersection numbers when (d, r) ≠ (2, 8). Since this exceptional case has been dealt with by Chang [6] this completes the characterization problem for Johnson graph.     

On Eckhoff's conjecture for Radon numbers; or how far the proof is still away

Eckhoff's conjecture for the Τ-Radon numbers r(Τ) of a convexity space. (X,C) says r(Τ) ≦ (r?1)(Τ?1)+1, with r = r(2). The main result of this note is that Eckhoff's conjecture is true in case ¦X¦ ≦ 2r and Τ = 3, i.e. each (2r?1)-set in a space with 2r?1 or 2r elements has a 3-Radon partition.     

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 .     

Pattern avoiding partitions and Motzkin left factors

Let L _n , n ≥ 1, denote the sequence which counts the number of paths from the origin to the line x = n ? 1 using (1, 1), (1, ?1), and (1, 0) steps that never dip below the x-axis (called Motzkin left factors). The numbers L _n count, among other things, certain restricted subsets of permutations and Catalan paths. In this paper, we provide new combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify four classes of the partitions of size n, all of which have cardinality L _n and each avoiding a set of two classical patterns of length four. We obtain a further generalization in one of the cases by considering a pair of statistics on the partition class. In a couple of cases, to show the result, we make use of the kernel method to solve a functional equation arising after a certain parameter has been introduced.     

The Zagier modification of Bernoulli numbers and a polynomial extension. Part I

The modified Bernoulli numbers $$ B_{n}^{*} = \sum_{r=0}^{n} \binom{n+r}{2r} \frac{B_{r}}{n+r}, \quad n > 0 $$ introduced by D. Zagier in 1998 are extended to the polynomial case by replacing B _r by the Bernoulli polynomials B _r (x). Properties of these new polynomials are established using the umbral method as well as classical techniques. The values of x that yield periodic subsequences $B_{2n+1}^{*}(x)$ are classified. The strange 6-periodicity of $B_{2n+1}^{*}$ , established by Zagier, is explained by exhibiting a decomposition of this sequence as the sum of two parts with periods 2 and 3, respectively. Similar results for modifications of Euler numbers are stated.     

Deficiency numbers of operators generated by infinite Jacobi matrices

New conditions for minimality, maximality, and nonmaximality of deficiency numbers of the minimal operator generated by the infinite Jacobi matrix with m × m matrix entries in the Hilbert space of mdimensional vectors are presented. Special attention is given to the case m = 1, i.e., to conditions on the elements of a tridiagonal numerical Jacobi matrix under which the determinate case of the classical power moment problem is realized.     

Modularity in random regular graphs and lattices

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.     

An entropy-theoretic proof of the Sucheston zero-one law

The purpose of this note is to provide a new proof to the following reformulation of the Sucheston zero-one law: An automorphism T of a Lebesgue space X is mixing if and only if, for every subsequence A of the sequence of natural numbers and every partition α of X having finite entropy, there exists a subsequence B = {b(j)} of A such that Λ_{r = 1}^∞ V_{j = r}^∞T^b(j)(α) is the trivial partition.     

Turán theorems and convexity invariants for directed graphs

This paper is motivated by the desire to evaluate certain classical convexity invariants (specifically, the Helly and Radon numbers) in the context of transitive closure of arcs in the complete digraph. To do so, it is necessary to establish several new Turán type results for digraphs and characterize the associated extremal digraphs. In the case of the Radon number, we establish the following analogue for transitive closure in digraphs of Radon's classical convexity theorem [J. Radon, Mengen konvexer Körper, die einer gemeinsamen Punkt enthalten, Math. Ann. 83 (1921) 113-115]: in a complete digraph on n?7 vertices with >n²/4 arcs, it is possible to partition the arc set into two subsets whose transitive closures have an arc in common.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Polynomiality of monotone Hurwitz numbers in higher genera

Hurwitz numbers count branched covers of the Riemann sphere with specified ramification, or equivalently, transitive permutation factorizations in the symmetric group with specified cycle types. Monotone Hurwitz numbers count a restricted subset of these branched covers, related to the expansion of complete symmetric functions in the Jucys–Murphy elements, and have arisen in recent work on the asymptotic expansion of the Harish-Chandra–Itzykson–Zuber integral. In previous work we gave an explicit formula for monotone Hurwitz numbers in genus zero. In this paper we consider monotone Hurwitz numbers in higher genera, and prove a number of results that are reminiscent of those for classical Hurwitz numbers. These include an explicit formula for monotone Hurwitz numbers in genus one, and an explicit form for the generating function in arbitrary positive genus. From the form of the generating function we are able to prove that monotone Hurwitz numbers exhibit a polynomiality that is reminiscent of that for the classical Hurwitz numbers, i.e.  , up to a specified combinatorial factor, the monotone Hurwitz number in genus g$g$ with ramification specified by a given partition is a polynomial indexed by g$g$ in the parts of the partition.     

A normalized representation of super splines of arbitrary degree on Powell–Sabin triangulations

In the paper, a family of bivariate super spline spaces of arbitrary degree defined on a triangulation with Powell–Sabin refinement is introduced. It includes known spaces of arbitrary smoothness r and degree \(3r-1\) but provides also other choices of spline degree for the same r which, in particular, generalize a known space of \(\mathscr {C}^{1}\) cubic super splines. Minimal determining sets of the proposed super spline spaces of arbitrary degree are presented, and the interpolation problems that uniquely specify their elements are provided. Furthermore, a normalized representation of the discussed splines is considered. It is based on the definition of basis functions that have local supports, are nonnegative, and form a partition of unity. The basis functions share numerous similarities with classical univariate B-splines.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.     

Independence for partition regular equations

A matrix A is said to be partition regular (PR) over a subset S of the positive integers if whenever S is finitely coloured, there exists a vector x, with all elements in the same colour class in S, which satisfies Ax=0. We also say that S is PR for A. Many of the classical theorems of Ramsey Theory, such as van der Waerden's theorem and Schur's theorem, may naturally be interpreted as statements about partition regularity. Those matrices which are partition regular over the positive integers were completely characterised by Rado in 1933.Given matrices A and B, we say that A Rado-dominates B if any set which is PR for A is also PR for B. One trivial way for this to happen is if every solution to Ax=0 actually contains a solution to By=0. Bergelson, Hindman and Leader conjectured that this is the only way in which one matrix can Rado-dominate another. In this paper, we prove this conjecture for the first interesting case, namely for 1×3 matrices. We also show that, surprisingly, the conjecture is not true in general.     

The structure of the distribution of a couple of observable random variables in credibility theory

We consider Bühlmann's classical model in credibility theory and we assume that the set of possible values of the observable random variables X₁, X₂,… is finite, say with n elements. Then the distribution of a couple (X_r, X_s) (r ≠ s) amounts to a square real matrix of order n, that we call a credibility matrix. In order to estimate credibility matrices or to adjust roughly estimated credibility matrices, we study the set of all credibility matrices and some particular subsets of it.     

Mixed partitions and related designs

We define a mixed partition of Π =  PG(d, q ^r ) to be a partition of the points of Π into subspaces of two distinct types; for instance, a partition of PG(2n ? 1, q ²) into (n ? 1)-spaces and Baer subspaces of dimension 2n ? 1. In this paper, we provide a group theoretic method for constructing a robust class of such partitions. It is known that a mixed partition of PG(2n ? 1, q ²) can be used to construct a (2n ? 1)-spread of PG(4n ? 1, q) and, hence, a translation plane of order q ²ⁿ . Here we show that our partitions can be used to construct generalized Andrè planes, thereby providing a geometric representation of an infinite family of generalized Andrè planes. The results are then extended to produce mixed partitions of PG(rn ? 1, q ^r ) for r ≥ 3, which lift to (rn ? 1)-spreads of PG(r ² n ? 1, q) and hence produce $2-(q^{r^2n},q^{rn},1)$ (translation) designs with parallelism. These designs are not isomorphic to the designs obtained from the points and lines of AG(r, q ^rn ).     

Terseness: Minimal idempotent generating sets for K(n,r)

Let n and r be positive integers with 1 < r < n and let K(n,r) consist of all transformations on X _n = {1,...,n} having image size less than or equal to r. For 1 < r < n, there exist rank-r elements of K(n,r) which are not the product of two rank-r idempotents. With this limitation in mind, we prove that for fixed r, and for all n large enough relative to r, that there exists a minimal idempotent generating set U of K(n,r) such that all rank-r elements of K(n,r) are contained in U ³. Moreover, for all n > r > 1, there exists a minimal idempotent generating set W for K(n,r) such that not every rank-r element is contained in W ³.     

Rainbow and monochromatic circuits and cocircuits in binary matroids

Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly $n?r$ colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.