Free Skew Boolean Intersection Algebras and Set Partitions

We show that atoms of the n-generated free left-handed skew Boolean intersection algebra are in a bijective correspondence with pointed partitions of non-empty subsets of \(\{1,2,\dots , n\}\). Furthermore, under the canonical inclusion into the k-generated free algebra, where k≥n, an atom of the n-generated free algebra decomposes into an orthogonal join of atoms of the k-generated free algebra in an agreement with the containment order on the respective partitions. As a consequence of these results, we describe the structure of finite free left-handed skew Boolean intersection algebras and express several their combinatorial characteristics in terms of Bell numbers and Stirling numbers of the second kind. We also look at the infinite case. For countably many generators, our constructions lead to the ‘partition analogue’ of the Cantor tree whose boundary is the ‘partition variant’ of the Cantor set.     

A weak Galerkin finite element method for the stokes equations

This paper introduces a weak Galerkin (WG) finite element method for the Stokes equations in the primal velocity-pressure formulation. This WG method is equipped with stable finite elements consisting of usual polynomials of degree k≥1 for the velocity and polynomials of degree k?1 for the pressure, both are discontinuous. The velocity element is enhanced by polynomials of degree k?1 on the interface of the finite element partition. All the finite element functions are discontinuous for which the usual gradient and divergence operators are implemented as distributions in properly-defined spaces. Optimal-order error estimates are established for the corresponding numerical approximation in various norms. It must be emphasized that the WG finite element method is designed on finite element partitions consisting of arbitrary shape of polygons or polyhedra which are shape regular.     

Multiplicative Properties of the Number of <Emphasis Type="Italic">k</Emphasis>-Regular Partitions

In a previous paper of the second author with K. Ono, surprising multiplicative properties of the partition function were presented. Here, we deal with k-regular partitions. Extending the generating function for k-regular partitions multiplicatively to a function on k-regular partitions, we show that it takes its maximum at an explicitly described small set of partitions, and can thus easily be computed. The basis for this is an extension of a classical result of Lehmer, from which an inequality for the generating function for k-regular partitions is deduced which seems not to have been noticed before.     

The Erdős‐Sós Conjecture for trees of diameter four

The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005     

Schur positivity and the <Emphasis Type="Italic">q</Emphasis>-log-convexity of the Narayana polynomials

We prove two recent conjectures of Liu and Wang by establishing the strong q-log-convexity of the Narayana polynomials, and showing that the Narayana transformation preserves log-convexity. We begin with a formula of Brändén expressing the q-Narayana numbers as a specialization of Schur functions and, by deriving several symmetric function identities, we obtain the necessary Schur-positivity results. In addition, we prove the strong q-log-concavity of the q-Narayana numbers. The q-log-concavity of the q-Narayana numbers N _q (n,k) for fixed k is a special case of a conjecture of McNamara and Sagan on the infinite q-log-concavity of the Gaussian coefficients.     

Brooks' Theorem and Beyond

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon–Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin–Kostochka Conjecture and Reed's Conjecture.     

An axiomatization of the Choquet integral in the context of multiple criteria decision making without any commensurability assumption

An axiomatization of the Choquet integral is proposed in the context of multiple criteria decision making without any commensurability assumption. The most essential axiom—named Commensurability Through Interaction—states that the importance of an attribute i takes only one or two values when a second attribute k varies. When the importance takes two values, the point of discontinuity is exactly the value on the attribute k that is commensurate to the fixed value on attribute i. If the weight of criterion i does not depend on criterion k, for any value of the other criteria than i and k, then criteria i and k are independent. Applying this construction to any pair i, k of criteria, one obtains a partition of the set of criteria. In each block, the criteria interact one with another, and it is thus possible to construct vectors of values on the attributes that are commensurate. There is complete independence between the criteria of any two blocks in this partition. Hence one cannot ensure commensurability between two blocks in the partition. But this is not a problem since the Choquet integral is additive between subsets of criteria that are independent.     

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.     

From recursions to asymptotics: Durfee and dilogarithmic deductions

We consider two dimensional arrays p(n,k) which count a family of partitions of n by a second parameter k, usually the number of parts. Such arrays frequently satisfy a finite recursion of a certain form, detailed in formula (2), as well as an asymptotic relation

(∗)

For such situations, we can characterize (Theorem 1) the function g(u) in terms of a polynomial associated with the recursion. We also identify (Theorem 2) a class of families which satisfy both the desired recursion and the limit law (*). For such families, the function g(u) is characterized by Theorem 1, and this resolves a number of conjectures made in an earlier work [Electron. J. Combin. 5 (1998) R32] concerning asymptotic enumeration of partitions by the size of their Durfee square. Finally, we study a family of partitions introduced by Andrews [Amer. J. Math. 91 (1969) 18–24]. These partitions do satisfy the desired recursion, but it is not known for sure whether they also satisfy the accompanying limit law. We prove (Theorem 3), conditionally on the conjectured limit law holding, some identities involving the dilogarithm. These identities are seen empirically, by calculation to many decimal places, to be true.     

Restricted <Emphasis Type="Italic">k</Emphasis>-color partitions

We generalize overpartitions to (k, j)-colored partitions: k-colored partitions in which each part size may have at most j colors. We find numerous congruences and other symmetries. We use a wide array of tools to prove our theorems: generating function dissections, modular forms, bijections, and other combinatorial maps. In the process of proving certain congruences, we find results of independent interest on the number of partitions with exactly 2 sizes of part in several arithmetic progressions. We find connections to divisor sums, the Han/Nekrasov–Okounkov hook length formula and a possible approach to finitization, and other topics, suggesting that a rich mine of results is available. We pose several immediate questions and conjectures.     

Maximally stable Gaussian partitions with discrete applications

Gaussian noise stability results have recently played an important role in proving results in hardness of approximation in computer science and in the study of voting schemes in social choice. We prove a new Gaussian noise stability result generalizing an isoperimetric result by Borell on the heat kernel and derive as applications:

Weighted Rogers–Ramanujan partitions and Dyson crank

In this paper, we refine a weighted partition identity of Alladi. We write formulas for generating functions for the number of partitions grouped with respect to a partition statistic other than the norm. We tie our weighted results as well as the different statistics with the crank of a partition. In particular, we prove that the number of partitions into even number of distinct parts whose odd-indexed parts’ sum is n is equal to the number of partitions of n with non-negative crank.     

Some inequalities for <Emphasis Type="Italic">k</Emphasis>-colored partition functions

Motivated by a partition inequality of Bessenrodt and Ono, we obtain analogous inequalities for k-colored partition functions \(p_{-k}(n)\) for all \(k\ge 2\). This enables us to extend the k-colored partition function multiplicatively to a function on k-colored partitions and characterize when it has a unique maximum. We conclude with one conjectural inequality that strengthens our results.     

Search-extension method for finding multiple solutions of nonlinear problem

Based on the eigensystem {λj,φj}of -Δ, the multiple solutions for nonlinear problem Δu f(u) = 0 in Ω, u = 0 on (?)Ωare approximated. A new search-extension method (SEM) is proposed, which consists of three algorithms in three level subspaces. Numerical experiments for f(u) = u3 in a square and L-shape domain are presented. The results show that there exist at least 3k - 1 distinct nonzero solutions corresponding to each κ-ple eigenvalue of -Δ(Conjecture 1).     

A Common Generalization to Theorems on Set Systems with <Emphasis Type="Italic">L</Emphasis>-intersections

In this paper, we provide a common generalization to the well-known Erdös–Ko–Rado Theorem, Frankl–Wilson Theorem, Alon–Babai–Suzuki Theorem, and Snevily Theorem on set systems with L-intersections. As a consequence, we derive a result which strengthens substantially the well-known theorem on set systems with k-wise L-intersections by Füredi and Sudakov [J. Combin. Theory, Ser. A, 105, 143–159 (2004)]. We will also derive similar results on L-intersecting families of subspaces of an n-dimensional vector space over a finite field F _q , where q is a prime power.     

More About 4-Isosceles Planar Sets

A finite planar set is k-isosceles for k 3 if every k-point subset of the set contains a point equidistant from the other two. In [1] Fishburn obtains several important results about isosceles planar sets and poses a series of conjectures and open questions. We disprove Conjecture 1 in [1] and provide another 34 nonsimilar 4-isosceles 8-point planar sets which answer one of the open questions in [1] negatively.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

Length-type parameters of finite groups with almost unipotent automorphisms

Let α be an automorphism of a finite group G. For a positive integer n, let E _G,n (α) be the subgroup generated by all commutators [...[[x,α],α],…,α] in the semidirect product G 〈α〉 over x ∈ G, where α is repeated n times. By Baer’s theorem, if E _G,n (α)=1, then the commutator subgroup [G,α] is nilpotent. We generalize this theorem in terms of certain length parameters of E _G,n (α). For soluble G we prove that if, for some n, the Fitting height of E _G,n (α) is equal to k, then the Fitting height of [G,α] is at most k + 1. For nonsoluble G the results are in terms of the nonsoluble length and generalized Fitting height. The generalized Fitting height h*(H) of a finite group H is the least number h such that F _h* (H) = H, where F ₀* (H) = 1, and F _i+1* (H) is the inverse image of the generalized Fitting subgroup F*(H/F _i *(H)). Let m be the number of prime factors of the order |α| counting multiplicities. It is proved that if, for some n, the generalized Fitting height E _G,n (α) of is equal to k, then the generalized Fitting height of [G,α] is bounded in terms of k and m. The nonsoluble length λ(H) of a finite group H is defined as the minimum number of nonsoluble factors in a normal series each of whose factors either is soluble or is a direct product of nonabelian simple groups. It is proved that if λE _G,n (α)= k, then the nonsoluble length of [G,α] is bounded in terms of k and m. We also state conjectures of stronger results independent of m and show that these conjectures reduce to a certain question about automorphisms of direct products of finite simple groups.     

Coloring Geometric Range Spaces

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ?² or ?³, we want to color them so that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c(k), or we require that the number of points in each region increases to p(k).Symmetrically, given a finite set of regions in ?² or ?³, we want to color them so that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks, and pseudo-disks. This is related to previous results of Pach, Tardos, and Tóth on decompositions of coverings.     

Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.