An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

-Operator frames for a Banach space

In this paper, (p,Y)-Bessel operator sequences, operator frames and (p,Y)-Riesz bases for a Banach space X are introduced and discussed as generalizations of the usual concepts for a Hilbert space and of the g-frames. It is proved that the set of all (p,Y)-Bessel operator sequences for a Banach space X is a Banach space and isometrically isomorphic to the operator space B(X,ℓ^p(Y)). Some necessary and sufficient conditions for a sequence of operators to be a (p,Y)-Bessel operator sequence are given. Also, a characterization of an independent (p,Y)-operator frame for X is obtained. Lastly, it is shown that an independent (p,Y)-operator frame for X is just a (p,Y)-Riesz basis for X and has a unique dual (q,Y^*)-operator frame for X^*.     

Functional central limit theorems for self-normalized least squares processes in regression with possibly infinite variance data

Based on an R²-valued random sample {(y_i,x_i),1≤i≤n} on the simple linear regression model y_i=x_iβ+α+ε_i with unknown error variables ε_i, least squares processes (LSPs) are introduced in D[0,1] for the unknown slope β and intercept α, as well as for the unknown β when α=0. These LSPs contain, in both cases, the classical least squares estimators (LSEs) for these parameters. It is assumed throughout that {(x,ε),(x_i,ε_i),i≥1} are i.i.d. random vectors with independent components x and ε that both belong to the domain of attraction of the normal law, possibly both with infinite variances. Functional central limit theorems (FCLTs) are established for self-normalized type versions of the vector of the introduced LSPs for (β,α), as well as for their various marginal counterparts for each of the LSPs alone, respectively via uniform Euclidean norm and sup–norm approximations in probability. As consequences of the obtained FCLTs, joint and marginal central limit theorems (CLTs) are also discussed for Studentized and self-normalized type LSEs for the slope and intercept. Our FCLTs and CLTs provide a source for completely data-based asymptotic confidence intervals for β and α.     

The intersection problem for m-cycle systems

Let I_m(v) denote the set of integers k for which a pair of m-cycle systems of K_v, exist, on the same vertex set, having k common cycles. Let J_m(v) = {0, 1, 2,…, t_v ?2, t_v} where t_v = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when I_m(2mn + x) = J_m(2mn + x), for both m even and m odd. Results include J^m(2mn + 1) = I^m(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K_2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc.     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

Automorphisms for Skew PBW Extensions and Skew Quantum Polynomial Rings

In this work, I study the automorphisms of skew PBW extensions and skew quantum polynomials. I use Artamonov's works as reference for getting the principal results about automorphisms for generic skew PBW extensions and generic skew quantum polynomials. In general, if I have an endomorphism on a generic skew PBW extension and there are some x _i , x _j , x _u such that the endomorphism is not zero on these elements and the principal coefficients are invertible, then endomorphisms act over x _i as a _i x _i for some a _i in the ring of coefficients. Of course, this is valid for quantum polynomial rings, with r = 0, as such Artamonov shows in his work. We use this result for giving some more general results for skew PBW extensions, using filtred-graded techniques. Finally, I use localization to characterize some class the endomorphisms and automorphisms for skew PBW extensions and skew quantum polynomials over Ore domains.     

Banach-stone theorems and separating maps

LetC(X,E) andC(Y,F) denote the spaces of continuous functions on the Tihonov spacesX andY, taking values in the Banach spacesE andF, respectively. A linear mapH:C(X,E)→C(Y,F) isseparating iff(x)g(x)=0 for allx inX impliesHf(y)Hg(y)=0 for ally inY. Some automatic continuity properties and Banach-Stone type theorems (i.e., asserting that isometries must be of a certain form) for separating mapsH between spaces of real- and complex-valued functions have already been developed. The extension of such results to spaces of vector-valued functions is the general subject of this paper. We prove in Theorem 4.1, for example, for compactX andY, that a linear isometryH betweenC(X,E) andC(Y,F) is a “Banach-Stone” map if and only ifH is “biseparating (i.e,H andH ⁻¹ are separating). The Banach-Stone theorems of Jerison and Lau for vector-valued functions are then deduced in Corollaries 4.3 and 4.4 for the cases whenE andF or their topological duals, respectively, are strictly convex. Research supported by the Fundació Caixa Castelló, MI/25.043/92     

On the number of list-colorings

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f(G, L) the number of L-colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k, f(G, L) = p(G, k), where P=G, k) is the chromatic polynominal of G. We denote by F(G, k) the minimum of f(G, L) over all the lists of boxes such that each box has size at least k. It is clear that F(G, k) ≤ P(G, k) for all G, k, and we will see in the introduction some examples of graphs such that F(G, k) < P(G, k) for some k. However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G, F(G, k) = P(G, k) for all k sufficiently large. It will follow in particular that F(G, k) is not given by a polynominal in k for all G. The proof is based on the analysis of an algorithm for computing f(G, L) analogous to the classical one for computing P(G, k).     

Condorcet proportions and Kelly's conjectures

Let C(m,n) be the proportion of all n-tuples of linear orders on a set of m alternatives such that some alternative x is ranked ahead of y in at least n of the orders, for each y≠x. Kelly proved that C(m,n)<C(m,r+1) for m3 and odd n 3, and that C(m,n)>C(m,n+1) for m3 and even n2. He also conjectured that C(m,n)>C(m+1,n) for m3 and n=3 or n5, and that C(m,n)>C(m,n+2) for m3 and n=1 or n3. The first of these conjectures is shown to be true for n=3. and for m=3 and odd n. The second conjecture is established for mε{3,4} and odd n, and for m=3 and all large even n.     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

Sur les algèbres absolument valuées qui vérifient l'identité (x, x, x) = 0

Let A denote a prehilbert absolute valued real algebra such that (x, x, x) = 0 for all x ε A; for this algebra we obtain the same results we have previously obtained for the flexible absolute valued algebra. Our main theorem is: A has a finite dimension 1, 2, 4 or 8, and is isotopic to or C. One of the results concerning the isomorphism between A and , C^*, or C shows that if for every two idempotents e₁ and e₂ in , then A is isomorphic to , C^*, or C. The example of infinite dimensional Hilbert absolute valued algebra given by Urbanik and Wright indicates that the assumption, (x, x, x) = 0 for all x ε A, is essential.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Torus quotients of homogeneous spaces — minimal dimensional Schubert varieties admitting semi-stable points

In this paper, for any simple, simply connected algebraic group G of type B,C or D and for any maximal parabolic subgroup P of G, we describe all minimal dimensional Schubert varieties in G/P admitting semistable points for the action of a maximal torus T with respect to an ample line bundle on G/P. We also describe, for any semi-simple simply connected algebraic group G and for any Borel subgroup B of G, all Coxeter elements τ for which the Schubert variety X(τ) admits a semistable point for the action of the torus T with respect to a non-trivial line bundle on G/B.     

Cohomological Characterizations of Biprojective and Biflat Banach Algebras

 Let A be a biprojective Banach algebra, and let A-mod-A be the category of Banach A-bimodules. In this paper, for every given -mod-A, we compute all the cohomology groups . Furthermore, we give some cohomological characterizations of biprojective Banach algebras. In particular, we show that the following properties of a Banach algebra A are equivalent to its biprojectivity: (i) for all -mod -A; (ii) for all -mod-A; (iii) for all -mod-A. (Here and are, respectively, the Banach A-bimodules of left, right and double multipliers of X.) Further, if A is a biflat Banach algebra and -mod-A, we compute all the cohomology groups , where is the Banach A-bimodule dual to X. Also, we give cohomological characterizations of biflat Banach algebras. We prove that a Banach algebra A is biflat if and only if any of the following conditions is valid: (i’) for all -mod-A; (ii’) for all -mod-A; (iii’) for all -mod-A.     

An introduction to presentations of monoid acts: quotients and subacts

The purpose of this article is to introduce the theory of presentations of monoids acts. We aim to construct “nice” general presentations for various act constructions pertaining to subacts and Rees quotients. More precisely, given an M-act A and a subact B of A, on the one hand, we construct presentations for B and the Rees quotient A/B using a presentation for A, and on the other hand, we derive a presentation for A from presentations for B and A/B. We also construct a general presentation for the union of two subacts. From our general presentations, we deduce a number of finite presentability results. Finally, we consider the case where a subact B has a finite complement in an M-act A. We show that if M is a finitely generated monoid and B is finitely presented, then A is finitely presented. We also show that if M belongs to a wide class of monoids, including all finitely presented monoids, then the converse also holds.     

A New Lower Bound on the Number of Odd Values of the Ordinary Partition Function

The parity of p(n), the ordinary partition function, has been studied for at least a century, yet it still remains something of a mystery. Although much work has been done, the known lower bounds for the number of even and odd values of p(n) for n ≤ N still appear to have a great deal of room for improvement. In this paper, we use classical methods to give a new lower bound for the number of odd values of p(n).     

Transcendence measures and algebraic growth of entire functions

In this paper we obtain estimates for certain transcendence measures of an entire function f. Using these estimates, we prove Bernstein, doubling and Markov inequalities for a polynomial P(z,w) in ℂ² along the graph of f. These inequalities provide, in turn, estimates for the number of zeros of the function P(z,f(z)) in the disk of radius r, in terms of the degree of P and of r. Our estimates hold for arbitrary entire functions f of finite order, and for a subsequence {n _j } of degrees of polynomials. But for special classes of functions, including the Riemann ζ-function, they hold for all degrees and are asymptotically best possible. From this theory we derive lower estimates for a certain algebraic measure of a set of values f(E), in terms of the size of the set E.     

On large sets of almost Hamilton cycle decompositions

A large set of CS(v, k, λ), k‐cycle system of order v with index λ, is a partition of all k‐cycles of K_v into CS(v, k, λ)s, denoted by LCS(v, k, λ). A (v ? 1)‐cycle is called almost Hamilton. The completion of the existence spectrum for LCS(v, v ? 1, λ) only depends on one case: all v ≥ 4 for λ = 2. In this article, it is shown that there exists an LCS(v, v ? 1,2) for any v ≡ 0,1 (mod 4) except v = 5, and for v = 6,7,10,11. © 2006 Wiley Periodicals, Inc. J Combin Designs 16: 53–69, 2008     

Recursive constructions for difference matrices and relative difference families

We present a new recursive construction for difference matrices whose application allows us to improve some results by D. Jungnickel. For instance, we prove that for any Abelian p-group G of type (n₁, n₂, …, n_t) there exists a (G, p^e, 1) difference matrix with e = Also, we prove that for any group G there exists a (G, p, 1) difference matrix where p is the smallest prime dividing |G|. Difference matrices are then used for constructing, recursively, relative difference families. We revisit some constructions by M. J. Colbourn, C. J. Colbourn, D. Jungnickel, K. T. Phelps, and R. M. Wilson. Combining them we get, in particular, the existence of a multiplier (G, k, λ)-DF for any Abelian group G of nonsquare-free order, whenever there exists a (p, k, λ)-DF for each prime p dividing |G|. Then we focus our attention on a recent construction by M. Jimbo. We improve this construction and prove, as a corollary, the existence of a (G, k, λ)-DF for any group G under the same conditions as above. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 165–182, 1998     

Spot Self-Replication and Dynamics for the Schnakenburg Model in a Two-Dimensional Domain

The dynamical behavior of multi-spot solutions in a two-dimensional domain Ω is analyzed for the two-component Schnakenburg reaction–diffusion model in the singularly perturbed limit of small diffusivity ε for one of the two components. In the limit ε→0, a quasi-equilibrium spot pattern in the region away from the spots is constructed by representing each localized spot as a logarithmic singularity of unknown strength S _j for j=1,…,K at unknown spot locations x _j ∈Ω for j=1,…,K. A formal asymptotic analysis, which has the effect of summing infinite logarithmic series in powers of −1/log ε, is then used to derive an ODE differential algebraic system (DAE) for the collective coordinates S _j and x _j for j=1,…,K, which characterizes the slow dynamics of a spot pattern. This DAE system involves the Neumann Green’s function for the Laplacian. By numerically examining the stability thresholds for a single spot solution, a specific criterion in terms of the source strengths S _j , for j=1,…,K, is then formulated to theoretically predict the initiation of a spot-splitting event. The analytical theory is illustrated for spot patterns in the unit disk and the unit square, and is compared with full numerical results computed directly from the Schnakenburg model.