An Erdős–Ko–Rado Theorem for Direct Products

Letn_i, k_ibe positive integers,i=1, ..., d,satisfyingn_i≥2k_i.LetX₁, ..., X_dbe pairwise disjoint sets with |X_i| =n_i.Letbe the family of those (k₁+···+k_d)-element sets which have exactlyk_ielements inX_i, i=1,..., d.It is shown that if⊂is an intersecting family then ||/||≤max_ik_i/n_i,and this is best possible. The proof is algebraic, although in thed=2 case a combinatorial argument is presented as well.     

Counting lattice chains and Delannoy paths in higher dimensions

Lattice chains and Delannoy paths represent two different ways to progress through a lattice. We use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in a lattice of arbitrary finite dimension. Specifically, fix nonnegative integers n₁,…,n_d, and let L denote the lattice of points (a₁,…,a_d)∈Z^d that satisfy 0≤a_i≤n_i for 1≤i≤d. We prove that the number of chains in L is given by where . We also show that the number of Delannoy paths in L equals Setting n_i=n (for all i) in these expressions yields a new proof of a recent result of Duchi and Sulanke [9] relating the total number of chains to the central Delannoy numbers. We also give a novel derivation of the generating functions for these numbers in arbitrary dimension.     

Unconditional constants and polynomial inequalities

If P is a polynomial on R^m of degree at most n, given by , and P_n(R^m) is the space of such polynomials, then we define the polynomial |P| by . Now if is a convex set, we define the norm on P_n(R^m), and then we investigate the inequality providing sharp estimates on for some specific spaces of polynomials. These ’s happen to be the unconditional constants of the canonical bases of the considered spaces.     

Some Best Constants in the Landau Inequality on a Finite Interval

An additive form of the Landau inequality forf∈Wⁿ_∞[−1, 1],is proved for 0<c?(cos(π/2n))⁻², 1?m?n−1, with equality forf(x)=T_n(1+(x−1)/c), 1?c?(cos(π/2n))⁻², whereT_nis the Chebyshev polynomial. From this follows a sharp multiplicative inequality,for ‖f⁽ⁿ⁾‖?σ ‖f‖, 2ⁿ⁻¹n! cos²ⁿ(π/2n)?σ?2ⁿ⁻¹n!, 1?m?n−1. For these values ofσ, the result confirms Karlin's conjecture on the Landau inequality for intermediate derivatives on a finite interval. For the proof of the additive inequality a Duffin and Schaeffer-type inequality for polynomials is shown.     

Families of low dimensional determinantal schemes

A scheme X⊂Pⁿ of codimension c is called standard determinantal if its homogeneous saturated ideal can be generated by the t×t minors of a homogeneous t×(t+c−1) matrix (f_ij). Given integers a₀≤a₁≤?≤a_t+c−2 and b₁≤?≤b_t, we denote by the stratum of standard determinantal schemes where f_ij are homogeneous polynomials of degrees a_j−b_i and is the Hilbert scheme (if n−c>0, resp. the postulation Hilbert scheme if n−c=0).Focusing mainly on zero and one dimensional determinantal schemes we determine the codimension of in and we show that is generically smooth along under certain conditions. For zero dimensional schemes (only) we find a counterexample to the conjectured value of appearing in Kleppe and Miró-Roig (2005) [25].     

Lattices generated by join of strongly closed subgraphs in d-bounded distance-regular graphs

Let Γ be a d-bounded distance-regular graph with diameter d?3. Suppose that P(x) is a set of all strongly closed subgraphs containing x and that P(x,i) is a subset of P(x) consisting of all elements of P(x) with diameter i. Let L^′(x,i) be the set generated by all joins of the elements in P(x,i). By ordering L^′(x,i) by inclusion or reverse inclusion, L^′(x,i) is denoted by or . We prove that and are both finite atomic lattices, and give the conditions for them both being geometric lattices. We also give the eigenpolynomial of      

Higher order log-concavity in Euler’s difference table

For 0≤k≤n, let be the entries in Euler’s difference table and let . Dumont and Randrianarivony showed equals the number of permutations on [n] whose fixed points are contained in {1,2,…,k}. Rakotondrajao found a combinatorial interpretation of the number in terms of k-fixed-points-permutations of [n]. We show that for any n≥1, the sequence is essentially 2-log-concave and reverse ultra log-concave.     

Transcendence of Binomial and Lucas' Formal Power Series

The formal power series[formula]is transcendental over (X) whentis an integer ≥ 2. This is due to Stanley forteven, and independently to Flajolet and to Woodcock and Sharif for the general case. While Stanley and Flajolet used analytic methods and studied the asymptotics of the coefficients of this series, Woodcock and Sharif gave a purely algebraic proof. Their basic idea is to reduce this series modulo prime numbersp, and to use thep-Lucas property: ifn = ∑n_ipⁱis the basepexpansion of the integern, then[equation]The series reduced modulopis then proved algebraic over _p(X), the field of rational functions over the Galois field _p, but its degree is not a bounded function ofp. We generalize this method to characterize all formal power series that have thep-Lucas property for “many” prime numbersp, and that are furthermore algebraic over (X).     

Bitableaux Bases for the Diagonally Invariant Polynomial Quotient Rings

LetR=Q[x₁, x₂, …, x_n,y₁, y₂, …, y_n,z₁, …, z_n,w₁, …, w_n], letR^S_n={P∈R:σP=P∀σ∈S_n} and letμandνbe hook shape partitions ofn. WithΔ_μ(X, Y) andΔ_ν(Z, W) being appropriately defined determinants, ∂_xibeing the partial derivative operator with respect tox_iandP(∂)=P(∂_x1, …, ∂_xn, ∂_y1, …, ∂_wn), define _{μ, ν}={P∈R^S_n:P(∂)Δ_μ(X, Y)Δ_ν(Z, W)=0}. A basis is constructed for the polynomial quotient ringR^S_n/_{μ, ν}that is indexed by pairs of standard tableaux. The Hilbert series ofR^S_n/_{μ, ν}is related to the Macdonaldq, t-Kostka coefficients.     

A combinatorial proof of the Dense Hindman’s Theorem

The Dense Hindman’s Theorem states that, in any finite coloring of the natural numbers, one may find a single color and a “dense” set B₁, for each b₁∈B₁ a “dense” set (depending on b₁), for each a “dense” set (depending on b₁,b₂), and so on, such that for any such sequence of b_i, all finite sums belong to the chosen color. (Here density is often taken to be “piecewise syndetic”, but the proof is unchanged for any notion of density satisfying certain properties.) This theorem is an example of a combinatorial statement for which the only known proof requires the use of ultrafilters or a similar infinitary formalism. Here we give a direct combinatorial proof of the theorem.     

A general iterative algorithm for nonexpansive mappings in Hilbert spaces

Let H be a real Hilbert space. Suppose that T is a nonexpansive mapping on H with a fixed point, f is a contraction on H with coefficient 0<α<1, and F:H→H is a k-Lipschitzian and η-strongly monotone operator with k>0,η>0. Let . We proved that the sequence {x_n} generated by the iterative method x_n+1=α_nγf(x_n)+(I−μα_nF)Tx_n converges strongly to a fixed point , which solves the variational inequality , for x∈F_ix(T).     

On the hyperbolicity constant in graphs

If X is a geodesic metric space and x₁,x₂,x₃∈X, a geodesic triangleT={x₁,x₂,x₃} is the union of the three geodesics [x₁x₂], [x₂x₃] and [x₃x₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if, for every geodesic triangle T in X, every side of T is contained in a δ-neighborhood of the union of the other two sides. We denote by δ(X) the sharpest hyperbolicity constant of X, i.e. . In this paper, we obtain several tight bounds for the hyperbolicity constant of a graph and precise values of this constant for some important families of graphs. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its number of edges, diameter and cycles. As a consequence of our results, we show that if G is any graph with m edges with lengths , then , and if and only if G is isomorphic to C_m. Moreover, we prove the inequality for every graph, and we use this inequality in order to compute the precise value δ(G) for some common graphs.     

Pósa-condition and nowhere-zero 3-flows

Let G be a simple graph on n vertices and π(G)=(d₁,d₂,…,d_n) be the degree sequence of G, where n≥3 and d₁≤d₂≤?≤d_n. The classical Pósa’s theorem states that if d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs.     

Independence results for variants of sharply bounded induction

The theory , axiomatized by the induction scheme for sharply bounded formulae in Buss’ original language of bounded arithmetic (with ⌊x/2⌋ but not ⌊x/2^y⌋), has recently been unconditionally separated from full bounded arithmetic S₂. The method used to prove the separation is reminiscent of those known from the study of open induction.We make the connection to open induction explicit, showing that models of can be built using a “nonstandard variant” of Wilkie’s well-known technique for building models of IOpen. This makes it possible to transfer many results and methods from open to sharply bounded induction with relative ease.We provide two applications: (i) the Shepherdson model of IOpen can be embedded into a model of , which immediately implies some independence results for ; (ii) extended by an axiom which roughly states that every number has a least 1 bit in its binary notation, while significantly stronger than plain , does not prove the infinity of primes.     

Constrained versions of Sauer’s lemma

Let [n]={1,…,n}. For a function h:[n]→{0,1}, x[n] and y{0,1} define by the width ω_h(x,y) of h at x the largest nonnegative integer a such that h(z)=y on x−a≤z≤x+a. We consider finite VC-dimension classes of functions h constrained to have a width ω_h(x_i,y_i) which is larger than N for all points in a sample or a width no larger than N over the whole domain [n]. Extending Sauer’s lemma, a tight upper bound with closed-form estimates is obtained on the cardinality of several such classes.