The worst case analysis of strong knapsack facets

In this paper we identify strong facet defining inequalities for the master knapsack polytope. Our computational experiments for small master knapsack problems show that 1 / k-facets for small values of k (\(k\le 4\)) are strong facets for the knapsack polytope. We show that this finding is robust by proving that the removal of these facets from the master knapsack polytope significantly weakens the resulting relaxation in the worst case. We show that the 1 / k-facets for \(k = 1\) are the strongest in that their removal from the master knapsack polytope weakens the relaxation by a factor of 3 / 2 in the worst case. We then show that the 1 / k-facets with \(k = 3\) or 4 are the next strongest. We also show that the strength of the 1 / k-facets weakens as k grows and that the 1 / k-facets with k even are stronger than the 1 / k-facets with k odd.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

On the Exact Maximum Complexity of Minkowski Sums of Polytopes

We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in ?³. In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m ₁,m ₂,…,m _k facets, respectively, is bounded from above by \(\sum_{1\leq i. Given k positive integers m ₁,m ₂,…,m _k , we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly \(\sum_{1\leq i. When k=2, for example, the expression above reduces to 4m ₁ m ₂?9m ₁?9m ₂+26.     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

Two remarks on iterates of Euler’s totient function

Let φ _k denote the kth iterate of Euler’s φ-function. We study two questions connected with these iterates. First, we determine the average order of φ _k and 1/φ _k ; e.g., we show that for each k ≥ 0,

$\sum_{n \leq x} \varphi_{k+1}(n) \sim \frac{3}{k! {\rm e}^{k\gamma}\pi^2}\frac{x^2}{(\log_3{x})^k}\qquad (x\to\infty),$

where γ is the Euler–Mascheroni constant. Second, for prime values of p, we study the number of distinct primes dividing \({\prod_{k=1}^{\infty}\varphi_k(p)}\). These prime divisors are precisely the primes appearing in the Pratt tree for p, which has been the subject of recent work by Ford, Konyagin, and Luca. We show that for each \({\epsilon > 0}\), the number of distinct primes appearing in the Pratt tree for p is \({ > ({\rm log}{p})^{1/2-\epsilon}}\) for all but x ^o(1) primes p ≤ x.

     

Congruences for Andrews’ (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">i</Emphasis>)-singular overpartitions

Andrews recently defined new combinatorial objects which he called (k, i)-singular overpartitions and proved that they are enumerated by \(\overline{C}_{k,i}(n)\) which is the number of overpartitions of n in which no part is divisible by k and only the parts \(\equiv \pm i \pmod {k}\) may be overlined. Andrews further showed that \(\overline{C}_{3,1}(n)\) satisfies some Ramanujan-type congruences modulo 3. In this paper, we show that for any pair (k, i), \(\overline{C}_{k,i}(n)\) satisfies infinitely many Ramanujan-type congruences modulo any power of prime coprime to 6k. We also show that for an infinite family of k, the value \(\overline{C}_{3k,k}(n)\) is almost always even. Finally, we investigate the parity of \(\overline{C}_{4k,k}\).     

Some irreducibility and indecomposability results for truncated binomial polynomials of small degree

In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every n≥k+2. Under the same assumption n≥k+2, we also show that the polynomial P _n,k cannot be expressed as a composition P _n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,n≥k+1 the roots of the polynomial P _m,k cannot be obtained from the roots of P _n,k , where m≠n, by a linear map.     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).     

Specialization results and ramification conditions

Given a hilbertian field k of characteristic zero and a finite Galois extension E/k(T) with group G such that E/k is regular, we produce some specializations of E/k(T) at points t0 ∈ P¹(k) which have the same Galois group but also specified inertia groups at finitely many given primes. This result has two main applications. Firstly we conjoin it with previous works to obtain Galois extensions of Q of various finite groups with specified local behavior — ramified or unramified — at finitely many given primes. Secondly, in the case k is a number field, we provide criteria for the extension E/k(T) to satisfy this property: at least one Galois extension F/k of group G is not a specialization of E/k(T).     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

Neighborhood Conditions for Fractional ID-<Emphasis Type="Italic">k</Emphasis>-factor-critical Graphs

Let G be a graph and k ≥ 2 a positive integer. Let h: E(G) → [0, 1] be a function. If \(\sum\limits_{e \mathrel\backepsilon x} {h(e) = k} \) holds for each x ∈ V (G), then we call G[F_h] a fractional k-factor of G with indicator function h where F_h = {e ∈ E(G): h(e) > 0}. A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical), if G ? I has a fractional k-factor for every independent set I of G. In this paper, we prove that if n ≥ 9k ? 14 and for any subset X ? V (G) we have

$${N_G}(X) = V(G)if|X| \geqslant \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ;or|{N_G}(X)| \geqslant \frac{{3k - 1}}{k}|X|if|X| < \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ,$$

then G is fractional ID-k-factor-critical.

     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.     

Generalisations of Hypomorphisms and Reconstruction of Hypergraphs

We define certain generalisations of hypergraph hypomorphisms, which we call k-morphisms, \((k,n-k)\)-hypomorphisms, partial \((k,n-k)\)-hypomorphisms. They are special bijections between collections of k-subsets of vertex sets of hypergraphs. We show that these mappings lead to alternative representations of the automorphism groups of r-uniform hypergraphs and vertex stabilisers of graphs. We also use them to show that almost every r-uniform hypergraph is reconstructible and \((k,n-k)\)-reconstructible. As a consequence we also obtain the result that almost every r-uniform hypergraph is asymmetric.     

Jacobi Maaß forms

In this paper, we give a new definition for the space of non-holomorphic Jacobi Maaß forms (denoted by J _k,m ^nh ) of weight k∈? and index m∈? as eigenfunctions of a degree three differential operator \(\mathcal{C}^{k,m}\). We show that the three main examples of Jacobi forms known in the literature: holomorphic, skew-holomorphic and real-analytic Eisenstein series, are contained in J _k,m ^nh . We construct new examples of cuspidal Jacobi Maaß forms F _f of weight k∈2? and index 1 from weight k?1/2 Maaß forms f with respect to Γ₀(4) and show that the map f ? F _f is Hecke equivariant. We also show that the above map is compatible with the well-known representation theory of the Jacobi group. In addition, we show that all of J _k,m ^nh can be “essentially” obtained from scalar or vector valued half integer weight Maaß forms.     

Locally 2-fold symmetric manifolds are locally symmetric

A manifold is locally k-fold symmetric if for any point and any k-dimensional vector subspace tangent to this point, there exists a local isometry such that this point is a fixed point and the differential of the isometry restricted to that k-dimensional vector subspace is minus the identity. We show that for \(k \ge 2\), Riemannian, pseudoriemannian, and Finslerian locally k-fold symmetric manifolds are locally symmetric.     

On the average volume of sections of convex bodies

The average section functional as(K) of a star body in Rn is the average volume of its central hyperplane sections: \(as\left( k \right) = \int_{{S^{n - 1}}} {\left| {K \cap {\xi ^ \bot }} \right|} d\sigma \left( \xi \right)\). We study the question whether there exists an absolute constantC > 0 such that for every n, for every centered convex body K in R ⁿ and for every 1 ≤ k ≤ n ? 2,

$$as\left( K \right) \leqslant {C^k}{\left| K \right|^{\frac{k}{n}}}\mathop {\max }\limits_{|E \in G{r_{n - k}}} {\kern 1pt} as\left( {K \cap E} \right)$$

. We observe that the case k = 1 is equivalent to the hyperplane conjecture. We show that this inequality holds true in full generality if one replaces C by CL _K orCd_ovr(K, BP _k ⁿ ), where L _K is the isotropic constant of K and dovr(K, BP _k ⁿ ) is the outer volume ratio distance of K to the class BP _k ⁿ of generalized k-intersection bodies. We also compare as(K) to the average of as(K ∩ E) over all k-codimensional sections of K. We examine separately the dependence of the constants on the dimension when K is in some classical position. Moreover, we study the natural lower dimensional analogue of the average section functional.

     

On Convex Geometric Graphs with no $$$$ Pairwise Disjoint Edges

A well-known result of Kupitz from 1982 asserts that the maximal number of edges in a convex geometric graph (CGG) on n vertices that does not contain \(k+1\) pairwise disjoint edges is kn (provided \(n>2k\)). For \(k=1\) and \(k=n/2-1\), the extremal examples are completely characterized. For all other values of k, the structure of the extremal examples is far from known: their total number is unknown, and only a few classes of examples were presented, that are almost symmetric, consisting roughly of the kn “longest possible” edges of CK(n), the complete CGG of order n. In order to understand further the structure of the extremal examples, we present a class of extremal examples that lie at the other end of the spectrum. Namely, we break the symmetry by requiring that, in addition, the graph admit an independent set that consists of q consecutive vertices on the boundary of the convex hull. We show that such graphs exist as long as \(q \le n-2k\) and that this value of q is optimal. We generalize our discussion to the following question: what is the maximal possible number f(n, k, q) of edges in a CGG on n vertices that does not contain \(k+1\) pairwise disjoint edges, and, in addition, admits an independent set that consists of q consecutive vertices on the boundary of the convex hull? We provide a complete answer to this question, determining f(n, k, q) for all relevant values of n, k and q.     

On Representation of a Solution to the Cauchy Problem by a Fourier Series in Sobolev-Orthogonal Polynomials Generated by Laguerre Polynomials

We consider the problem of representing a solution to the Cauchy problem for an ordinary differential equation as a Fourier series in polynomials l _r,k ^α (x) (k = 0, 1,...) that are Sobolev-orthonormal with respect to the inner product

$$\left\langle {f,g} \right\rangle = \sum\limits_{v = 0}^{r - 1} {{f^{(v)}}(0){g^{(v)}}} (0) + \int\limits_0^\infty {{f^{(r)}}(t)} {g^{(r)}}(t){t^\alpha }{e^{ - t}}dt$$

, and generated by the classical orthogonal Laguerre polynomials L _k ^α (x) (k = 0, 1,...). The polynomials l _r,k ^α (x) are represented as expressions containing the Laguerre polynomials L _n ^α?r (x). An explicit form of the polynomials l _r,k+r ^α (x) is established as an expansion in the powers x ^r+l , l = 0,..., k. These results can be used to study the asymptotic properties of the polynomials l _r,k ^α (x) as k→∞and the approximation properties of the partial sums of Fourier series in these polynomials.