An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

The connectivity of a graph on uniform points on [0,1]

A random graph G_n(x) is constructed on independent random points U₁,…,U_n distributed uniformly on [0,1]^d, d1, in which two distinct such points are joined by an edge if the l_∞-distance between them is at most some prescribed value 0<x<1. The connectivity distance c_n, the smallest x for which G_n(x) is connected, is shown to satisfy

(1)

For d2, the random graph G_n(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: c_n/d_n→1, a.s., as n→∞, where d_n is the largest nearest-neighbor link, the smallest x for which G_n(x) has no isolated vertices.     

Intersections of nest algebras in finite dimensions

If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f₁,f₂,…,f_n} of H and a permutation π such that and where M_i=  span{f₁,f₂,…,f_i} and N_i= span{f_π(1),f_π(2),…,f_π(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=n−j+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.     

A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

A sufficient and necessary condition for an OWA bag mapping having the self-identity

A mapping ƒ : _n=1^∞Iⁿ → I is called a bag mapping having the self-identity if for every (x₁,…,x_n) ε _i=1^∞Iⁿ we have (1) ƒ(x₁,…,x_n) = ƒ(x_i1,…,x_in) for any arrangement (i₁,…,i_n) of {1,…,n}; monotonic; (3) ƒ(x₁,…,x_n, ƒ(x₁,…,x_n)) = ƒ(x₁,…,x_n). Let {ω_i,n : I = 1,…,n;n = 1,2,…} be a family of non-negative real numbers satisfying Σ_i=1ⁿω_i,n = 1 for every n. Then one calls the mapping ƒ : _i=1^∞Iⁿ → I defined as follows an OWA bag mapping: for every (x₁,…,x_n) ε _i=1^∞Iⁿ, ƒ(x₁,…,x_n) = Σ_i=1ⁿω_i,ny_i, where y_i is the it largest element in the set {x₁,…,x_n}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

A theorem on independence

Suppose we are given a family of sets , where S(j) = ∩^k_i=1 H_i(j), and suppose each collection of sets H_i(j₁),…,H_i(j_k+1) has a lower bound under the partial ordering defined by inclusion, then the maximal size of an independent subcollection of is k. For example, for a fixed collection of half-spaces H₁,…,H_k in , we define to be the collection of all sets of the form

where χ_i, I=1,…, k are points in . Then the maximal size of an independent collection of such sets us k. This leads to a proof of the bound of 2d due to Rényi et al. (1951) for the maximum size of an independent family of rectangles in with sides parallel to the coordinate axes, and to a bound of d+1 for the maximum size of an independent family of simplices in with sides parallel to given hyperplanes H₁,…,H_d+1.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

Measurements of edge-uncolorability

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let c_k be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r₃=|E|−c₃ and . We show that on one side r₃ and r₂ bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r₃ and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr₃. For k=2,3, let ζ_k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.     

Resolutions of Stanley-Reisner rings and Alexander duality

Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal I_Δ in the polynomial ring A = k[x₁, …, x_n], and its quotient k[Δ] = A/I_Δ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ^* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dim_k Tor_i^A (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ^*. As corollaries, we prove that I_Δ has a linear resolution as A-module if and only if Δ^* is Cohen-Macaulay over k, and show how to compute the Betti numbers dim_k Tor_i^A (k[Δ],k) in some cases where Δ^* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.     

Cyclic coloring of plane graphs

Let G be a plane graph, and let χ_k(G) be the minimum number of colors to color the vertices of G so that every two of them which lie in the boundary of the same face of the size at most k, receive different colors. In 1966, Ore and Plummer proved that χ_k(G)2k for any k3. It is also known that χ₃(G)4 (Appel and Haken, 1976) and χ₄(G)6 (Borodin, 1984). The result in the present paper is: χ₅(G)9, χ₆(G)11, χ₇(G)12, and χ_k(G)2k − 3 if k8.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

Efficient robust estimation of parameter in the random censorship model

For an open set Θ of ^k, let \s{P_θ: θ Θ\s} be a parametric family of probabilities modeling the distribution of i.i.d. random variables X₁,…, X_n. Suppose X_i's are subject to right censoring and one is only able to observe the pairs (min(X_i, Y_i), [X_i Y_i]), i = 1,…, n, where [A] denotes the indicator function of the event A, Y₁,…, Y_n are independent of X₁,…, X_n and i.i.d. with unknown distribution Q₀. This paper investigates estimation of the value θ that gives a fitted member of the parametric family when the distributions of X₁ and Y₁ are subject to contamination. The constructed estimators are adaptive under the semi-parametric model and robust against small contaminations: they achieve a lower bound for the local asymptotic minimax risk over Hellinger neighborhoods, in the Hájel—Le Cam sense. The work relies on Beran (1981). The construction employs some results on product-limit estimators.     

The game of n-times nim

The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f₁,f₂,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size f_i. It is proved that there exist constants c=c(n) and k₀=k₀(n) such that f_k+1=f_k+f_k−c for all k>k₀, and lim_n→∞ c(n)/(nlogn)=1.     

Weak convergence to the multiple Stratonovich integral

We have considered the problem of the weak convergence, as tends to zero, of the multiple integral processes

in the space , where fL²([0,T]ⁿ) is a given function, and {η(t)}_>0 is a family of stochastic processes with absolutely continuous paths that converges weakly to the Brownian motion. In view of the known results when n2 and f(t₁,…,t_n)=1_{t1<t2<<tn}, we cannot expect that these multiple integrals converge to the multiple Itô–Wiener integral of f, because the quadratic variations of the η are null. We have obtained the existence of the limit for any {η}, when f is given by a multimeasure, and under some conditions on {η} when f is a continuous function and when f(t₁,…,t_n)=f₁(t₁)f_n(t_n)1_{t1<t2<<tn}, with f_iL²([0,T]) for any i=1,…,n. In all these cases the limit process is the multiple Stratonovich integral of the function f.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.