Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

Torsion points of elliptic curves over large algebraic extensions of finitely generated fields

The following Theorem is proved:Let K be a finitely generated field over its prime field. Then, for almost all e-tuples (σ)=(σ ₁, …,σ _e)of elements of the abstract Galois group G(K)of K we have:

1. If e=1,then E _tor(K(σ))is infinite. Morover, there exist infinitely many primes l such that E(K(σ))contains points of order l.
2. If e≧2,then E _tor(K(σ))is finite.
3. If e≧1,then for every prime l, the group E(K(σ))contains only finitely many points of an l-power order.

HereK(σ) is the fixed field in the algebraic closureK ofK, ofσ ₁, …,σ _e, and “almost all” is meant in the sense of the Haar measure ofG(K).     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Amalgamations of almost regular edge-colourings of simple graphs

A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets S₁, …, S_n and identifying the vertices in S_i to form a single vertex α_i for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of S_i to an element of S_j in F will join α_i to α_j in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that V(G(L)) = V(G), E(G(L)) = L. We call a graph almost regular if there is an integer d such that every vertex has valency d or d + 1. Suppose that E(G) is partitioned into disjoint sets E₁, …, E_r. Hilton [3] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with 2r + 1 vertices and F(E_i) is a Hamilton circuit of F for i = 1, …, r. We give a new proof of Hilton's theorem, which also yields a generalisation. Specifically, for any q ∈ {0, 1, …, r}, we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that F(E₁), …, F(E_r) are almost regular and F(E₁), …, F(E_q) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

Cellularity of first countable spaces

In this paper, we find subspaces of the Pixley-Roy space on the irrationals which are

• 1.(1) a first countable ccc space which does not have a σ-linked base,
• 2.(2) for each n>1, a first countable space which has a σ-n-linked base but which does not have a (σ−n+1)-linked base and
• 3.(3) a first countable space which has, for each n>1, a σ-n-linked base but which does not have a σ-centered base.

It is consistent with ¬CH that (1) and (2) have cardinality ℵ₁. (3) is constructed from a graph G on the continuum c which is not the union of countably many complete subgraphs but has no uncountable pairwise incompatible family of finite complete subgraphs (complete subgraphs A and B are compatible if there is a complete subgraph C which contains A and B).     

On a certain type of commutators of operators

LetH be a separable infinite-dimensional Hilbert space and letC be a normal operator andG a compact operator onH. It is proved that the following four conditions are equivalent.

1. C +G is a commutatorAB-BA with self-adjointA.
2. There exists an infinite orthonormal sequencee _j inH such that |Σ _j ⁿ =1 (Ce _j, e_j)| is bounded.
3. C is not of the formC ₁ ⊕C ₂ whereC ₁ has finite dimensional domain andC ₂ satisfies inf {|(C ₂ x, x)|: ‖x‖=1}>0.
4. 0 is in the convex hull of the set of limit points of spC.

     

Note on the longest paths in {K 1,4, K 1,4 + e}-free graphs

A graph G is {K 1,4,K 1,4 + e}-free if G contains no induced subgraph isomorphic to K 1,4 or K 1,4 + e.In this paper,we show that G has a path which is either hamiltonian or of length at least 2δ(G) + 2 if G is a connected {K 1,4,K 1,4 + e}-free graph on at least 7 vertices.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

r-Numbers completion problems of partial upper canonical form I

A pair (A, B), where A is an n × n matrix and B is an n × m matrix, is said to have the nonnegative integers sequence {r_j}_j=1^p as the r-numbers sequence if r₁ = rank(B) and r_j = rank[B AB … A^j−1 B] − rank[B AB … A^j−2B], 2 ≤ j ≤ p. Given a partial upper triangular matrix A of size n × n in upper canonical form and an n × m matrix B, we develop an algorithm that obtains a completion A_c of A, such that the pair (A^c, B) has an r-numbers sequence prescribed under some restrictions.     

Vertex-antimagic labelings of regular graphs

Let G = (V, E) be a finite, simple and undirected graph with p vertices and q edges. An (a, d)-vertex-antimagic total labeling of G is a bijection f from V (G) ∪ E(G) onto the set of consecutive integers 1, 2, . . . , p + q, such that the vertex-weights form an arithmetic progression with the initial term a and difference d, where the vertex-weight of x is the sum of the value f (x) assigned to the vertex x together with all values f (xy) assigned to edges xy incident to x. Such labeling is called super if the smallest possible labels appear on the vertices. In this paper, we study the properties of such labelings and examine their existence for 2r-regular graphs when the difference d is 0, 1, . . . , r + 1.     

On the chromaticity of the 2-degree integral subgraph ofq-trees

A graphG is called to be a 2-degree integral subgraph of aq-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactlyq- 1 triangles. An added-vertexq-treeG with n vertices is obtained by taking two verticesu, v (u, v are not adjacent) in a q-treesT withn -1 vertices such that their intersection of neighborhoods ofu, v forms a complete graphK _q , and adding a new vertexx, new edgesxu, xv, xv ₁,xv ₂, …,xv _{q- 4}, where {v ₁,v ₂,...,v _q?4} ?-K _q . In this paper we prove that a graphG with minimum degree not equal toq -3 and chromatic polynomialP(G;λ) = λ(λ - 1) … (λ -q +2)(λ -q +1)³(λ -q) ^{n- q- 2} withn ≥ q + 2 has and only has 2-degree integral subgraph of q-tree withn vertices and added-vertex q-tree withn vertices.     

A characterization of Riesz spaces which are Riesz isomorphic to C(X) for some completely regular space X

Let E be an Archimedean Riesz space possessing a weak unit e and let Ω be the collection of all Riesz homomorphisms ø from E onto ℝ such that ø(e)=1. The Gelfand mapping G :x→x^ on E is defined by x^(ø) = ø(x) for all ø∈Ω. We endow Ω with the topology induced by E (i.e., the weakest topology such that each x^ is continuous on Ω). The principal ideal in E generated by e is denoted by I_d(e). The main theorem in this paper says that the following statements (A) and (B) are equivalent.

• (A)There exists a completely regular space X such that E is Riesz isomorphic to the space C(X) of all real continuous functions on X.
• (B)The following conditions for the Riesz space E hold: (1) E is Archimedean and has a weak unit e; (2) Ω separates the points of E; (3) E is uniformly complete; (4) G(I_d(e)) is norm dense in the space C_b(Ω) of all real bounded continuous functions on Ω; (5) E is 2-universally complete with carrier space Ω.

Some other conditions are mentioned and an example is given to show that condition (5) is necessary for (B) ⇒(A).     

A complete set of invariants for finite groups and other results

For a finite group G and a set I ? {1, 2,…, n} let

${}_{\mathrm{G}}\text{(n,I) = ∑}{}_{\mathrm{g\; \in \; G}}\text{ε}{}_1\text{(g)?ε}{}_2\text{(g)???ε}{}_{\mathrm{n}}\text{(g)}$

,where

$\text{ε}{}_{\mathrm{i}}\text{(g)=g}\text{if}\text{i=∈ I,}$

$\text{ε}{}_{\mathrm{l}}\text{(g)=l}\text{if}\text{i=∈ I.}$

We prove, among other results, that the positive integers

$\text{tr}\text{(e}{}_{\mathrm{G}}\text{(n,I}{}_1\text{)+?+e}{}_{\mathrm{G}}\text{(n,I}{}_{\mathrm{r}}\text{))}{}^{\mathrm{k}}\text{:n,r,k,?1, I}{}_{\mathrm{j}}\text{?{1,…,n}, 1?|i}{}_{\mathrm{j}}\text{|?3}$

for 1 ? j ? r, I_j1 ∩ I_j2 ∩ I_j3 ∩ I_j4 = Ø for any 1 ? j₁ <j₂ <j₃ <j₄ ? r, determine G up to isomorphism. We also show that under certain assumptions finite groups are determined up to isomorphism by the number of their subgroups.     

Cubic planar hamiltonian graphs of various types

Let U be the set of cubic planar hamiltonian graphs, A the set of graphs G in U such that G-v is hamiltonian for any vertex v of G, B the set of graphs G in U such that G-e is hamiltonian for any edge e of G, and C the set of graphs G in U such that there is a hamiltonian path between any two different vertices of G. With the inclusion and/or exclusion of the sets A,B, and C, U is divided into eight subsets. In this paper, we prove that there is an infinite number of graphs in each of the eight subsets.     

New families of graceful banana trees

Consider a family of stars. Take a new vertex. Join one end-vertex of each star to this new vertex. The tree so obtained is known as abanana tree. It is proved that the banana trees corresponding to the family of stars

1. (K_1,1, K_1,2,…, K_{1,t ?1}, (α + l) K_1,t, K_{1,t + 1}, …, K_1,n), α ? 0
2. (2K_1,1, 2K_1,2,…, 2K_{1,t? 1}, (α + 2)K_1,t, 2K_{1,t + 1, …}, 2K_1,n), 0 ? α <t and
3. (3K_1,t, 3K_1,2, …, 3K_1,n) are graceful.

     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

Non-linear Approximations Using Sets of Finite Cardinality or Finite Pseudo-dimension

We investigate optimal non-linear approximations of multivariate periodic functions with mixed smoothness. In particular, we study optimal approximation using sets of finite cardinality (as measured by the classical entropy number), as well as sets of finite pseudo-dimension (as measured by the non-linear widths introduced by Ratsaby and Maiorov). Approximation error is measured in the L_q(T^d)-sense, where T^d is the d-dimensional torus. The functions to be approximated are in the unit ball SB^r_p, θ of the mixed smoothness Besov space or in the unit ball SW^r_p of the mixed smoothness Sobolev space. For 1<p, q<∞, 0<θ⩽∞ and r>0 satisfying some restrictions, we establish asymptotic orders of these quantities, as well as construct asymptotically optimal approximation algorithms. We particularly prove that for either r>1/p and θ⩾p or r>(1/p−1/q)₊ and θ⩾min{q, 2}, the asymptotic orders of these quantities for the Besov class SB^r_p, θ are both n^−r(log n)^{(d−1)(r+1/2−1/θ)}.     

On the h-triangles of sequentially (S r ) simplicial complexes via algebraic shifting

Recently, Haghighi, Terai, Yassemi, and Zaare-Nahandi introduced the notion of a sequentially (S _r ) simplicial complex. This notion gives a generalization of two properties for simplicial complexes: being sequentially Cohen–Macaulay and satisfying Serre’s condition (S _r ). Let Δ be a (d?1)-dimensional simplicial complex with Γ(Δ) as its algebraic shifting. Also let (h _i,j (Δ))_{0≤j≤i≤d} be the h-triangle of Δ and (h _i,j (Γ(Δ)))_{0≤j≤i≤d} be the h-triangle of Γ(Δ). In this paper, it is shown that for a Δ being sequentially (S _r ) and for every i and j with 0≤j≤i≤r?1, the equality h _i,j (Δ)=h _i,j (Γ(Δ)) holds true.