Order Ideals in Weak Subposets of Young’s Lattice and Associated Unimodality Conjectures

The k-Young lattice Y^k is a weak subposet of the Young lattice containing partitions whose first part is bounded by an integer k > 0. The Y^k poset was introduced in connection with generalized Schur functions and later shown to be isomorphic to the weak order on the quotient of the affine symmetric group S_{k + 1} by a maximal parabolic subgroup. We prove a number of properties for Y^k including that the covering relation is preserved when elements are translated by rectangular partitions with hook-length k. We highlight the order ideal generated by an m x n rectangular shape. This order ideal, L^k(m, n), reduces to L(m, n) for large k, and we prove it is isomorphic to the induced subposet of L(m, n) whose vertex set is restricted to elements with no more than k - m + 1 parts smaller than m. We provide explicit formulas for the number of elements and the rank-generating function of L^k(m, n). We conclude with unimodality conjectures involving q-binomial coefficients and discuss how implications connect to recent work on sieved q-binomial coefficients.AMS Subject Classification: 06A06, 05A17, 05A10, 05E05.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the number of conjugacy classes of maximal subgroups in a finite soluble group

We show that for many formations \frak F\frak F, there exists an integer n = [`(m)](\frak F)n = \overline m(\frak F) such that every finite soluble group G not belonging to the class \frak F\frak F has at most n conjugacy classes of maximal subgroups belonging to the class \frak F\frak F. If \frak F\frak F is a local formation with formation function f, we bound [`(m)](\frak F)\overline m(\frak F) in terms of the [`(m)](f(p))(p ? \Bbb P )\overline m(f(p))(p \in \Bbb P ). In particular, we show that [`(m)](\frak N^k) = k+1\overline m(\frak N^k) = k+1 for every nonnegative integer k, where \frak N^k\frak N^k is the class of all finite groups of Fitting length ￡ k\le k.     

Lower bounds for coverings of pairs by large blocks

Letnkt be positive integers, andX—a set ofn elements. LetC(n, k, t) be the smallest integerm such that there existm k-tuples ofX B ₁ B ₂,...,B _m with the property that everyt-tuple ofX is contained in at least oneB _i . It is shown that in many cases the standard lower bound forC(n, k, 2) can be improved (k sufficiently large,n/k being fixed). Some exact values ofC(n, k, 2) are also obtained.     

Lotto design tables

An LD(n,k,p,t;b) lotto design is a set of b k‐sets (blocks) of an n‐set such that any p‐set intersects at least one k‐set in t or more elements. Let L(n,k,p,t) denote the minimum number of blocks in any LD(n,k,p,t;b) lotto design. We will list the known lower and upper bound theorems for lotto designs. Since many of these bounds are recursive, we will incorporate this information in a set of tables for lower and upper bounds for lotto designs with small parameters. We will also use back‐track algorithms, greedy algorithms, and simulated annealing to improve the tables. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 335–359, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10020     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Arithmetical identities of the Brauer-Rademacher type

Summary LetA be a regular arithmetical convolution andk a positive integer. LetA _k (r) = {d: d ^k A(r ^k )}, and letf A _k g denote the convolution of arithmetical functionsf andg with respect toA _k . A pair (f, g) of arithmetical functions is calledadmissible if(f A _k g)(m) 0 for allm and if the functions satisfy an arithmetical functional equation which generalizes the Brauer—Rademacher identity. Necessary and sufficient conditions are found for a pair (f, g) of multiplicative functions to be admissible, and it follows that, if(f A _k g)(m) 0 f(m) for allm, then (f, g) is admissible if and only if itsdual pair (f A _k g, g ^–1 ) is admissible.Iff andg ^–1 areA _k -multiplicative (a condition stronger than being multiplicative), and(f A _k g)(m) 0 for allm, then (f, g) is admissible, calledCohen admissible. Its dual pair is calledSubbarao admissible. If (f A _k g) ^–1 (m) 0 itsinverse pair (g ^–1 , f ^–1 ) is also Cohen admissible.Ifg is a multiplicative function then there exists a multiplicative functionf such that the pair (f, g) is admissible if and only if for everyA _k -primitive prime powerp ⁱ either (i)g(p ⁱ ) 0 or (ii)g(p ) = 0 for allp havingA _k -type equal tot. There is a similar kind of characterization of the multiplicative functions which are first components of admissible pairs of multiplicative functions. IfA _k is not the unitary convolution, then there exist multiplicative functionsg which satisfy (i) and are such that neitherg norg ^–1 isA _k -multiplicative: hence there exist admissible pairs of multiplicative functions which are neither Cohen admissible nor Subbarao admissible.An arithmetical functionf is said to be anA _k -totient if there areA _k -multiplicative functionsf _T andf _V such thatf = f _T A _k f _V ^-1 Iff andg areA _k -totients with(f A _k g)(m) 0 for allm, and iff _V = g _T , then the pair (f, g) is admissible. The class of such admissible pairs includes many pairs which are neither Cohen admissible nor Subbarao admissible. If (f, g) is a pair in this class, and iff(m), (f A _k g) ^–1 (m), g ^–1 (m),f ^–1 (m) andg(m) are all nonzero for allm, then its dual, its inverse, the dual of its inverse, the inverse of its dual and the inverse of the dual of its inverse are also admissible, and in many cases these six pairs are distinct.A number of related results, and many examples, are given.     

Upper bounds on the sum of powers of the degrees of a simple planar graph

For a simple planar graph G and a positive integer k, we prove the upper bound 2(n ? 1)^k + 4^k(n ? 4) + 2·3^k ? 2((δ + 1)^k ? δ^k)(3n ? 6 ? m) on the sum of the kth powers of the degrees of G, where n, m, and δ are the order, the size, and the minimum degree of G, respectively. The bound is tight for all m with 0?3n ? 6 ? m≤?n/2? ? 2 and δ = 3. We also present upper bounds in terms of order, minimum degree, and maximum degree of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:112‐123, 2011     

On degrees of maps between Grassmannians

Let G_n,k denote the oriented grassmann manifold of orientedk-planes in ℝⁿ. It is shown that for any continuous mapf: G_n,k → G_n,k, dim G_n,k = dim G_m,l = l(m −l), the Brouwer’s degree is zero, providedl > 1,n ≠ m. Similar results for continuous mapsg: ℂG_m,l → ℂG_n,k,h: ℍG_m,l → ℍG_n,k, 1 ≤ l < k ≤ n/2, k(n — k) = l(m — l) are also obtained.     

The Number of Congruent Simplices in a Point Set

   Abstract. For 1 ≤ k≤ d-1 , let f _k ^(d) (n) be the maximum possible number of k -simplices spanned by a set of n points in R ^d that are congruent to a given k -simplex. We prove that f ₂ ⁽³⁾ (n) = O(n ^5/3 2 ^O(α2(n)) ) , f ₂ ⁽⁴⁾ (n) = O(n^ 2+ ɛ ) , for any ɛ >0 , f ₂ ⁽⁵⁾ (n) = Θ(n ^7/3 ) , and f ₃ ⁽⁴⁾ (n) = O(n^ 20/9+ ɛ ) , for any ɛ >0 . We also derive a recurrence to bound f _k ^(d) (n) for arbitrary values of k and d , and use it to derive the bound f _k ^(d) (n) = O(n^ d/2+ ɛ ) , for any ɛ >0 , for d ≤ 7 and k ≤ d-2 . Following Erdos and Purdy, we conjecture that this bound holds for larger values of d as well, and for k≤ d-2 .     

On an adjacency property of graphs

A graph G has property A(m, n, k) if for any sequence of m + n distinct points of G, there are at least k other points, each of which is adjacent to the first m points of the sequence but not adjacent to any of the latter n points. the minimum order among all graphs with property A(m, n, k) is denoted a(m, n, k). Bounds are given on the numbers a(m, n, k) and some exact results are indicated.     

The Number of Congruent Simplices in a Point Set

Abstract. For 1 ≤ k≤ d-1 , let f _k ^(d) (n) be the maximum possible number of k -simplices spanned by a set of n points in R ^d that are congruent to a given k -simplex. We prove that f ₂ ⁽³⁾ (n) = O(n ^5/3 2 ^O(α2(n)) ) , f ₂ ⁽⁴⁾ (n) = O(n^ 2+ ɛ ) , for any ɛ >0 , f ₂ ⁽⁵⁾ (n) = Θ(n ^7/3 ) , and f ₃ ⁽⁴⁾ (n) = O(n^ 20/9+ ɛ ) , for any ɛ >0 . We also derive a recurrence to bound f _k ^(d) (n) for arbitrary values of k and d , and use it to derive the bound f _k ^(d) (n) = O(n^ d/2+ ɛ ) , for any ɛ >0 , for d ≤ 7 and k ≤ d-2 . Following Erdos and Purdy, we conjecture that this bound holds for larger values of d as well, and for k≤ d-2 .     

Solution of a covering problem related to labelled tournaments

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m ≤ (^k+1₂) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = O(k²/log k). We give explicit tournaments with m = k^2−o(1). If the number of vertices is bounded by N < 2^k₁ we have a better upper bound of m = O(k log N), which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k − 1. © 1996 John Wiley & Sons, Inc.     

Explicit congruences for the partition function modulo every prime

Let p(n) denote the number of unrestricted partitions of the positive integer n, and let m be a prime $\geq 13$. We prove, for k = 1, explicit congruences of the form where $r_{m,k}, \delta_{m,k}$ are integers depending on m and k and $\phi_{m,k}(z)$ are explicitly computable level one holomorphic modular forms of small weight. We also give theoretical and numerical support that the congruences also hold for k > 1. Our main idea is a level reduction result for the modular forms which originated from Atkin-Lehner. From our result, we deduce periodicity properties for the partition function with short periods which improve upon recent results of K. Ono. Received: 24 January 2002     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is -hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k=1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.     

Fonctions de partitions à parité périodique

Let be the set of positive integers and a subset of . For , let denote the number of partitions of n with parts in . In the paper J. Number Theory 73 (1998) 292, Nicolas et al. proved that, given any and , there is a unique set , such that is even for n>N. Soon after, Ben Saïd and Nicolas (Acta Arith. 106 (2003) 183) considered , and proved that for all k≥0, the sequence is periodic on n. In this paper, we generalise the above works for any formal power series f in with f(0)=1, by constructing a set such that the generating function of is congruent to f modulo 2, and by showing that if f=P/Q, where P and Q are in with P(0)=Q(0)=1, then for all k≥0 the sequence is periodic on n.     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

New Ore‐Type Conditions for H‐Linked Graphs

For a fixed (multi)graph H, a graph G is H‐linked if any injection f: V(H)→V(G) can be extended to an H‐subdivision in G. The notion of an H ‐linked graph encompasses several familiar graph classes, including k‐linked, k‐ordered and k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012