Self-complementary totally symmetric plane partitions

A totally symmetric plane partition of size n is a plane partition whose three-dimensional Ferrers graph is contained in the box X_n = [1, n] × [1, n] × [1, n] and which is mapped to itself under all permutations of the coordinate axes. The complement of the Ferrers graph of such a plane partition (that is, the set of lattice points in the box X_n that do not belong to the Ferrers graph) is again totally symmetric when viewed from the vantage point of the vertex (n + 1, n + 1, n + 1). A totally symmetric plane partition is self-complementary if it is congruent (in the geometrical sense) to its complement. This cannot occur unless n = 2m is even. In this paper we give several conjectures and a few theorems concerning self-complementary totally symmetric plane partitions. In particular we describe evidence which indicates a close relationship with m by m alternating sign matrices. In an earlier paper we described the close connection between m by m alternating sign matrices and descending plane partitions with no parts exceeding m. We are thus left with three classes of objects which are all apparently interrelated. There remain many unsolved problems, the simplest of which is to prove that any two of the objects have the same cardinality.     

Isometric embeddings of finite metric spaces

It is proved that there exists a metric on a Cantor set such that any finite metric space whose diameter does not exceed 1 and the number of points does not exceed n can be isometrically embedded into it. It is also proved that for any m, n ∈ N there exists a Cantor set in R^m that isometrically contains all finite metric spaces which can be embedded into R^m, contain at most n points, and have the diameter at most 1. The latter result is proved for a wide class of metrics on R^m and, in particular, for the Euclidean metric.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

On the size of the Durfee square of a random integer partition

We prove a local limit theorem for the length of the side of the Durfee square in a random partition of a positive integer n as n→∞. We rely our asymptotic analysis on the power series expansion of x^m2∏_j=1^m(1−x^j)⁻² whose coefficient of xⁿ equals the number of partitions of n in which the Durfee square is m².     

On periodic groups of odd period n ≥ 1003

In the paper, using the Adyan-Lysenok theorem claiming that, for any odd number n ≥ 1003, there is an infinite group each of whose proper subgroups is contained in a cyclic subgroup of order n, it is proved that the set of groups with this property has the cardinality of the continuum (for a given n). Further, it is proved that, for m ≥ k ≥ 2 and for any odd n ≥ 1003, the m-generated free n-periodic group is residually both a group of the above type and a k-generated free n-periodic group, and it does not satisfy the ascending and descending chain conditions for normal subgroups either.     

On the total positivity of restricted Stirling numbers

This note shows that the matrix whose (n,k) entry is the number of set partitions of {1,…,n} into k blocks with size at most m is never totally positive for m≥3; thus answering a question posed in [H. Han, S. Seo, Combinatorial proofs of inverse relations and log-concavity for Bessel numbers, European J. Combin. 29 (2008) 1544-1554].     

A generalization of Turán's theorem to directed graphs

We consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on m vertices. For an integer n?2, let T_n denote the transitive tournament with vertex set X_n={1,2,3,…,n} and edge set {(i,j):1?i<j?n}. A subgraph H of T_n is said to be m-locally unipathic when the restriction of H to each m element subset of X_n consisting of m consecutive integers is unipathic. We show that the maximum number of edges in a m-locally unipathic subgraph of T_n is ($\text{q}\text{2}\text{)(m?1)}{}^2\text{+q(m?1)r+?}\text{1}\text{4}\text{r}{}^2\text{?}$ where n= q(m?1+r and $\text{?}\text{1}\text{2}\text{(m?1)??r<?}\text{3}\text{2}\text{(m?1)?}$. As is the case with Turán's theorem, the extremal graphs for our problem are complete multipartite graphs. Unlike Turán's theorem, the part sizes will not be uniform. The proof of our principal theorem rests on a combinatorial theory originally developed to investigate the rank of partially ordered sets.     

The conjugate trace and trace of a plane partition

The conjugate trace and trace of a plane partition are defined, and the generating function for the number of plane partitions π of n with ?r rows and largest part ?m, with conjugate trace t (or trace t, when m = ∞), is found. Various properties of this generating function are studied. One consequence of these properties is a formula which can be regarded as a q-analog of a well-known result arising in the representation theory of the symmetric group.     

The Turán problem for projective geometries

We consider the following Turán problem. How many edges can there be in a (q+1)-uniform hypergraph on n vertices that does not contain a copy of the projective geometry PG_m(q)? The case q=m=2 (the Fano plane) was recently solved independently and simultaneously by Keevash and Sudakov (The Turán number of the Fano plane, Combinatorica, to appear) and Füredi and Simonovits (Triple systems not containing a Fano configuration, Combin. Probab. Comput., to appear). Here we obtain estimates for general q and m via the de Caen-Füredi method of links combined with the orbit-stabiliser theorem from elementary group theory. In particular, we improve the known upper and lower bounds in the case q=2, m=3.     

On the largest prime factor of the partition function of n

Let p(n) be the function that counts the number of partitions of n. For a positive integer m, let P(m) be the largest prime factor of m. Here, we show that P(p(n)) tends to infinity when n tends to infinity through some set of asymptotic density 1. In fact, we show that the inequality P(p(n))>loglogloglogloglogn holds for almost all positive integers n. Features of the proof are the first term in Rademacher??s formula for p(n), Gowers?? effective version of Szemerédi??s theorem, and a classical lower bound for a nonzero homogeneous linear form in logarithms of algebraic numbers due to Matveev.     

Generalized euler-type partition identities

Let A and S be subsets of the natural numbers. Let A′(n) be the number of partitions of n where each part appears exactly m times for some m?A. Let S(n) be the number of partitions of n into parts which are elements of S.     

The <Emphasis Type="Italic">m</Emphasis>th Largest and <Emphasis Type="Italic">m</Emphasis>th Smallest Parts of a Partition

The theory of overpartitions is applied to determine formulas for the number of partitions of n where (1) the mth largest part is k and (2) the mth smallest part is k.     

Critical Partitions and Nodal Deficiency of Billiard Eigenfunctions

The paper addresses the nodal count (i.e., the number of nodal domains) for eigenfunctions of Schr?dinger operators with Dirichlet boundary conditions in bounded domains. The classical Sturm theorem states that in dimension one, the nodal and eigenfunction counts coincide: the nth eigenfunction partitions the interval into n nodal domains. The Courant Nodal Theorem claims that in any dimension, the number of nodal domains ?? _n of the nth eigenfunction cannot exceed n. However, it follows from an asymptotically stronger upper bound by Pleijel that in dimensions higher than 1 the equality can hold for only finitely many eigenfunctions. Thus, in most cases a ??nodal deficiency?? d _n ?=?n??? _n arises. One can say that the nature of the nodal deficiency has not been understood. It was suggested in recent years that, rather than starting with eigenfunctions, one can look at partitions of the domain into ?? sub-domains, asking which partitions can correspond to eigenfunctions, and what would be the corresponding deficiency. To this end one defines an ??energy?? of a partition, for example, the maximum of the ground state energies of the sub-domains. One notices that if a partition does correspond to an eigenfunction, then the ground state energies of all the nodal domains are the same, i.e., it is an equipartition. It was shown in a recent paper by Helffer, Hoffmann-Ostenhof and Terracini that (under some natural conditions) partitions minimizing the energy functional correspond to the ??Courant sharp?? eigenfunctions, i.e. to those with zero nodal deficiency. In this paper it is shown that it is beneficial to restrict the domain of the functional to the equipartition, where it becomes smooth. Then, under some genericity conditions, the nodal partitions correspond exactly to the critical points of the functional. Moreover, the nodal deficiency turns out to be equal to the Morse index at the corresponding critical point. This explains, in particular, why the minimal partitions must be Courant sharp.     

Erd?s–Szekeres Theorem for Point Sets with Forbidden Subconfigurations

According to the Erd?s?CSzekeres theorem, every set of n points in the plane contains roughly logn points in convex position. We investigate how this bound changes if our point set does not contain a subset that belongs to a fixed order type.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

On lines, joints, and incidences in three dimensions

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) [9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R³ and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R³. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) [9].     

On tricyclic graphs whose second largest eigenvalue does not exceed 1

A tricyclic graph of order n is a connected graph with n vertices and n + 2 edges. In this paper, all tricyclic graphs whose second largest eigenvalue does not exceed 1 are identified.     

Balanced partitions

A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. We begin by establishing a less well-known companion result, which states that both of these quantities are equal to the number of partitions of n into even parts along with exactly one triangular part. We then introduce the characteristic of a partition, which is determined in a simple way by the placement of odd parts within the list of all parts. This leads to a refinement of the aforementioned result in the form of a new type of partition identity involving characteristic, distinct parts, even parts, and triangular numbers. Our primary purpose is to present a bijective proof of the central instance of this new type of identity, which concerns balanced partitions—partitions in which odd parts occupy as many even as odd positions within the list of all parts. The bijection is accomplished by means of a construction that converts balanced partitions of 2n into unrestricted partitions of n via a pairing of the squares in the Young tableau.