Perfect codes in direct products of cycles—a complete characterization

Let be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓ_i is a multiple of rⁿ+(r+1)ⁿ. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.     

Hamiltonicity and restricted block-intersection graphs of -designs

Given a combinatorial design with block set , its traditional block-intersection graph is the graph having vertex set such that two vertices b₁ and b₂ are adjacent if and only if b₁ and b₂ have non-empty intersection. In this paper, we consider the S-block-intersection graph, in which two vertices b₁ and b₂ are adjacent if and only if |b₁∩b₂|S. As our main result, we prove that {1,2,…,t−1}-block-intersection graphs of t-designs with parameters (v,t+1,λ) are Hamiltonian whenever t3 and vt+3, except possibly when (v,t){(8,5),(7,4),(7,3),(6,3)}.     

Orthogonal graphs of odd characteristic and their automorphisms

The (isotropic) orthogonal graph O(2ν+δ,q) over of odd characteristic, where ν1 and δ=0,1 or 2 is introduced. When ν=1, O(21+δ,q) is a complete graph. When ν2, O(2ν+δ,q) is strongly regular and its parameters are computed, as well as its chromatic number. The automorphism groups of orthogonal graphs are also determined.     

disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

Meinardus' theorem on weighted partitions: Extensions and a probabilistic proof

The number c_n of weighted partitions of an integer n, with parameters (weights) b_k, k1, is given by the generating function relationship . Meinardus (1954) established his famous asymptotic formula for c_n, as n→∞, under three conditions on power and Dirichlet generating functions for the sequence b_k. We give a probabilistic proof of Meinardus' theorem with weakened third condition and extend the resulting version of the theorem from weighted partitions to other two classic types of decomposable combinatorial structures, which are called assemblies and selections.     

Regularity of smooth curves in biprojective spaces

Maclagan and Smith [D. Maclagan, G.G. Smith, Multigraded Castelnuovo–Mumford regularity, J. Reine Angew. Math. 571 (2004) 179–212] developed a multigraded version of Castelnuovo–Mumford regularity. Based on their definition we will prove in this paper that for a smooth curve (a,b2) of bidegree (d₁,d₂) with nondegenerate birational projections the ideal sheaf is (d₂−b+1,d₁−a+1)-regular. We also give an example showing that in some cases this bound is the best possible.     

Rational Approximation with Varying Weights III

Approximation by weighted rationals of the form wⁿr_n, where r_n=p_n/q_n, p_n and q_n are polynomials of degree at most [αn] and [βn], respectively, and w is an admissible weight, is investigated on compact subsets of the real line for a general class of weights and given α0, β0, with α+β>0. Conditions that characterize the largest sets on which such approximation is possible are given. We apply the general theorems to Laguerre and Freud weights.     

On the chromatic number of an oriented matroid

We prove that the chromatic number of an oriented matroid of rank r3 is at most r+1 with equality if and only if is the oriented matroid of an orientation of K_r+1, the complete graph on r+1 vertices.     

Polar SAT and related graphs

We introduce polar SAT and show that a general SAT can be reduced to it in polynomial time. A set of clauses C is called polar if there exists a partition C^pCⁿ=C, called a polar partition, such that each clause in C^p involves only positive (i.e., non-complemented) variables, while each clause in Cⁿ contains only negative (i.e., complemented) variables. A polar set of clauses C=(C^p,Cⁿ) is called (p,n)-polar, where p1 and n1, if each clause in C^p (respectively, in Cⁿ) contains exactly p (respectively, exactly n) literals. We classify all (p,n)-polar SAT Problems according to their complexity. Specifically, a (p,n)-Polar SAT problem is NP-complete if either p>n2 or n>p2. Otherwise it can be solved in polynomial time. We introduce two new hereditary classes of graphs, namely polar satgraphs and polar (3,2)-satgraphs, and we characterize them in terms of forbidden induced subgraphs. Both characterization involve an infinite number of minimal forbidden induced subgraphs. As are result, we obtain two narrow hereditary subclasses of weakly chordal graphs where Independent Domination is an NP-complete problem.     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.