Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

The domination numbers of the 5 × n and 6 × n grid graphs

The k × n grid graph is the product P_k × P_n of a path of length k ? 1 and a path of length n ? 1. We prove here formulas found by E. O. Hare for the domination numbers of P₅ × P_n and P₆ × P_n. © 1993 John Wiley & Sons, Inc.     

Maximal regular subsemigroups of certain semigroups of transformations

Let T _n and P _n be the full and partial transformation semigroups on a finite set of order n respectively. The properties of the subsemigroups of T _n and P _n have been widely studied. But the maximal regular subsemigroups of T _n and P _n seem to be unknown. In this note, we determine all the maximal regular subsemigroups of all ideals of T _n and P _n . April 7, 1999     

A rigidity theorem for the pair ${\cal q}{\Bbb C} P^n$ (complex hyperquadric, complex projective space)

Given a compact Kähler manifold M of real dimension 2n, let P be either a compact complex hypersurface of M or a compact totally real submanifold of dimension n. Let q\cal q (resp. \Bbb R Pⁿ{\Bbb R} P^n) be the complex hyperquadric (resp. the totally geodesic real projective space) in the complex projective space \Bbb C Pⁿ{\Bbb C} P^n of constant holomorphic sectional curvature 4l \lambda . We prove that if the Ricci and some (n-1)-Ricci curvatures of M (and, when P is complex, the mean absolute curvature of P) are bounded from below by some special constants and volume (P) / volume (M) ￡\leq volume (q\cal q)/ volume (\Bbb C Pⁿ)({\Bbb C} P^n) (resp. ￡\leq volume (\Bbb R Pⁿ)({\Bbb R} P^n) / volume (\Bbb C Pⁿ)({\Bbb C} P^n)), then there is a holomorphic isometry between M and \Bbb C Pⁿ{\Bbb C} P^n taking P isometrically onto q\cal q (resp. \Bbb R Pⁿ{\Bbb R} P^n). We also classify the Kähler manifolds with boundary which are tubes of radius r around totally real and totally geodesic submanifolds of half dimension, have the holomorphic sectional and some (n-1)-Ricci curvatures bounded from below by those of the tube \Bbb R Pⁿ_r{\Bbb R} P^n_r of radius r around \Bbb R Pⁿ{\Bbb R} P^n in \Bbb C Pⁿ{\Bbb C} P^n and have the first Dirichlet eigenvalue not lower than that of \Bbb R Pⁿ_r{\Bbb R} P^n_r.     

Characterization of a class of triangle-free graphs with a certain adjacency property

Let m and n be nonnegative integers. Denote by P(m,n) the set of all triangle-free graphs G such that for any independent m-subset M and any n-subset N of V(G) with M ∩ N = Ø, there exists a unique vertex of G that is adjacent to each vertex in M and nonadjacent to any vertex in N. We prove that if m ? 2 and n ? 1, then P(m,n) = Ø whenever m ? n, and P(m,n) = {K_m,n+1} whenever m > n. We also have P(1,1) = {C₅} and P(1,n) = Ø for n ? 2. In the degenerate cases, the class P(0,n) is completely determined, whereas the class P(m,0), which is most interesting, being rich in graphs, is partially determined.     

Notes on Free Monadic Boolean Algebras

If F B(2 ⁿ – 1) denotes the Boolean algebra with 2 ⁿ – 1 free generators and P(2 ⁿ ) is the Cartesian product of 2 ⁿ Boolean algebras all equal to F B(2 ⁿ – 1), we define on P(2 ⁿ ) an existential quantifier by means of a relatively complete Boolean subalgebra of P(2 ⁿ ) and we prove that (P(2ⁿ),) is the monadic Boolean algebra with n free generators. Every element of P(2 ⁿ ) is a 2 ⁿ -tuple whose coordinates are in F B(2 ⁿ – 1); in particular, so are the n generators of P(2 ⁿ ). We indicate in this work the coordinates of the n generators of P(2 ⁿ ).     

Characterizations of cyclic polytopes

Let P denote a simplicial convex 2m-polytope with n vertices. Then the following are equivalent: (i) P is cyclic; (ii) P satisfies Gale’s Evenness Condition; (iii) Every subpolytope of P is cyclic; (iv) P has at least 2m+2 cyclic subpolytopes with n−1 vertices if n ≥ 2m+5; (v) P is neighbourly and has n universal edges. We present an additional characterization based upon an easily described point arrangement property.     

Test for properness using residue calculus

We will consider global problems in the ringK[X ₁, …,X _n] on the polynomials with coefficients in a subfieldK ofC. LetP=(P ₁, …,P _n):K ⁿ →K ⁿ be a polynomial map such that (P ₁,…,P _n) is a quasi-regular sequence generating a proper ideal, the main thing we do is to use the algebraic residues theory (as described in [5]) as a computational tool to give some result to test when a map (P ₁, …,P _n) is a proper map by computing a finite number of residue symbols.     

On the Maximum Number of Translates in a Point Set

Given a finite set P⊆ℝ ^d , called a pattern, t _P (n) denotes the maximum number of translated copies of P determined by n points in ℝ ^d . We give the exact value of t _P (n) when P is a rational simplex, that is, the points of P are rationally affinely independent. In this case, we prove that t _P (n)=n−m _r (n), where r is the rational affine dimension of P, and m _r (n) is the r -Kruskal–Macaulay function. We note that almost all patterns in ℝ ^d are rational simplices. The function t _P (n) is also determined exactly when | P |≤3 or when P has rational affine dimension one and n is large enough. We establish the equivalence of finding t _P (n) and the maximum number s _R (n) of scaled copies of a suitable pattern R⊆ℝ⁺ determined by n positive reals. As a consequence, we show that s_Ak(n)=n-\varTheta (n^1-1/p(k))s_{A_{k}}(n)=n-\varTheta (n^{1-1/\pi(k)}) , where A _k ={1,2,…,k} is an arithmetic progression of size k, and π(k) is the number of primes less than or equal to k.     

On Linear Groups of Degree 2n Containing a Representation of the Special Linear Group of Degree n

Let n be an integer, n ≥ 2, and let a field P be a quadratic extension of an infinite field k. Regarding P as a k-vector space of dimension 2, we consider an n-dimensional P-vector space V as a 2n-dimensional k-vector space so the general linear group GL _n (P) acting on V is embedded in the group GL _2n (k). Let a field K be an algebraic extension of k. In this article, we determine overgroups of the special linear group SL _n (P) in the group GL _2n (K).     

Polytopes of partitions of numbers

We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope P_n is the convex hull of the set of incidence vectors of all partitions n=x₁+2x₂++nx_n. We show that the sequence P₁,P₂,…,P_n,… can be treated as an embedded chain. The dynamics of behavior of the vertices of P_n, as n increases, is established. Some sufficient and some necessary conditions for a point of P_n to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of P_n. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p₀=p_n and p_i+p_n−i=p_n,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope P_n. All vertices and facets of P_n for n≤8 and n≤6, respectively, are presented.     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in \Bbb R³{\Bbb R}^3 with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense.     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤2 andx _ij −x _ik −x _jk ≤0 for 1≤i, j, k≤n. Hence, the metric polytopeM _n , defined as the solution set of the triangle inequalities, is a relaxation ofP _n .We consider several properties of geometric type forP _n , in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k≤log₂ n, satisfying some additional assumption, determines a simplicial face ofMn and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum ofP _n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.     

Extremal functions of forbidden double permutation matrices

We say a 0–1 matrix A avoids a matrix P if no submatrix of A can be transformed into P by changing some ones to zeroes. We call P an m-tuple permutation matrix if P can be obtained by replacing each column of a permutation matrix with m copies of that column. In this paper, we investigate n×n matrices that avoid P and the maximum number ex(n,P) of ones that they can have. We prove a linear bound on ex(n,P) for any 2-tuple permutation matrix P, resolving a conjecture of Keszegh [B. Keszegh, On linear forbidden matrices, J. Combin. Theory Ser. A 116 (1) (2009) 232–241]. Using this result, we obtain a linear bound on ex(n,P) for any m-tuple permutation matrix P. Additionally, we demonstrate the existence of infinitely many minimal non-linear patterns, resolving another conjecture of Keszegh from the same paper.     

Properties of tangential and cyclic polygons: an application of circulant matrices

In this paper, the properties of tangential and cyclic polygons proposed by Lopez-Real are proved rigorously using the theory of circulant matrices. In particular, the concepts of slippable tangential polygons and conformable cyclic polygons are defined. It is shown that an n-sided tangential (or cyclic) polygon P _n with n even is slippable (or conformable) and the sum of a set of non-adjacent sides (or interior angles) of P _n satisfies certain equalities. On the other hand, for a tangential (or cyclic) polygon P _n with n odd, it is rigid and the sum of a set of non-adjacent sides (or interior angles) of P _n satisfies certain inequalities. These inequalities give a definite answer to the question raised by Lopez-Real concerning the alternating sum of interior angles of a cyclic polygon.     

Regular Polytopes of Nearly Full Rank

An abstract regular polytope P\mathcal{P} of rank n can only be realized faithfully in Euclidean space \mathbbE^d\mathbb{E}^{d} of dimension d if d≥n when P\mathcal{P} is finite, or d≥n−1 when P\mathcal{P} is infinite (that is, P\mathcal{P} is an apeirotope). In case of equality, the realization P of P\mathcal{P} is said to be of full rank. If there is a faithful realization P of P\mathcal{P} of dimension d=n+1 or d=n (as P\mathcal {P} is finite or not), then P is said to be of nearly full rank. In previous papers, all the at most four-dimensional regular polytopes and apeirotopes of nearly full rank have been classified. This paper classifies the regular polytopes and apeirotopes of nearly full rank in all higher dimensions.     

Maximizing the distance between center,centroid and characteristic set of a tree

Consider a tree P_n-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2,?…?,n-g] vertices by adding g pendant vertices to the pendant vertex n-g. We prove that over all trees on n?≥?5 vertices, the distance between center and characteristic set, centroid and characteristic set, and center and centroid is maximized by trees of the form P_n-g,g , 2?≤?g?≤?n-3. For n≥ 5, we also supply the precise location of the characteristic set of the tree P_n-g,g , 2?≤?g?≤?n-3.     

A parallel derangement generation algorithm

A parallel algorithm to generate allD _n derangements ofn distinct elements is presented in this paper. The algorithm requiresO([D _n /P]nlogn) time whenP processors are available on a Single Instruction Multiple Data Stream (SIMD) computer.     

Blocking Visibility for Points in General Position

For a finite set P in the plane, let b(P) be the smallest possible size of a set Q, Q∩P=∅, such that every segment with both endpoints in P contains at least one point of Q. We raise the problem of estimating b(n), the minimum of b(P) over all n-point sets P with no three points collinear. We review results providing bounds on b(n) and mention some additional observations.