The Riemannian product structures of spacelike hypersurfaces with constant k-th mean curvature in the de Sitter spaces

In this paper, we investigate complete spacelike hypersurfaces in the de Sitter space with constant k-th mean curvature and two distinct principal curvatures one of which is simple. We obtain some characterizations of the Riemannian product H¹(c₁)×Sn−1(c₂) or Hn−1(c₁)×S¹(c₂) in the de Sitter space .     

Note on robust critical graphs with large odd girth

A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn² edges.     

The number of k-colorings of a graph on a fixed surface

We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2ⁿ distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2ⁿ distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5.     

A study on monotone self-dual Boolean functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).     

Preserving Z-sets by Dranishnikov's resolution

We prove that Dranishnikov's k-dimensional resolution is a UV^n − 1-divider of Chigogidze's k-dimensional resolution ck. This fact implies that preserves Z-sets. A further development of the concept of UV^n − 1-dividers permits us to find sufficient conditions for to be homeomorphic to the Nöbeling space νk or the universal pseudoboundary σk. We also obtain some other applications.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

For a given permutation matrix P, let fP(n) be the maximum number of 1-entries in an n×n(0,1)-matrix avoiding P and let SP(n) be the set of all n×n permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that cP:=limn→∞fP(n)/n is finite, while the Stanley-Wilf conjecture asserts that is finite.In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture.We focus on the values of the Stanley-Wilf limit (sP) and the Füredi-Hajnal limit (cP). We improve the reduction and obtain which decreases the general upper bound on sP from sP?constconstO(klog(k)) to sP?constO(klog(k)) for any k×k permutation matrix P. In the opposite direction, we show .For a lower bound, we present for each k a k×k permutation matrix satisfying cP=Ω(k²).     

Minimizing a monotone concave function with laminar covering constraints

Let V be a finite set with |V|=n. A family F⊆2^V is called laminar if for all two sets X,Y∈F, X∩Y≠∅ implies X⊆Y or X⊇Y. Given a laminar family F, a demand function , and a monotone concave cost function , we consider the problem of finding a minimum-cost such that x(X)?d(X) for all X∈F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n²q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any . We also prove that if F is given by an oracle, then it takes Ω(n²q) time to solve the problem, which implies that our O(n²q) time algorithm is optimal in this case. Furthermore, we propose an algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires Ω(2^n/2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.     

Hypersurfaces with constant mean curvature in a hyperbolic space

Let Mⁿ be an n-dimensional complete connected and oriented hypersurface in a hyperbolic space Hⁿ⁺¹（c） with non-zero constant mean curvature H and two distinct principal curvatures. In this paper, we show that （1） if the multiplicities of the two distinct principal curvatures are greater than 1,then Mⁿ is isometric to the Riemannian product S^k（r）×H^n-k（-1/（r² + ρ²））, where r > 0 and 1 < k < n - 1;（2）if H² > -c and one of the two distinct principal curvatures is simple, then Mⁿ is isometric to the Riemannian product S^n-1（r） × H¹（-1/（r² +ρ²）） or S¹（r） × H^n-1（-1/（r² +ρ²））,r > 0, if one of the following conditions is satisfied （i） S≤（n-1）t²2+c²t^-22 on Mⁿ or （ii）S≥ （n-1）t²1+c²t^-21 on Mⁿ or（iii）（n-1）t²2+c²t^-22≤ S≤（n-1）t²1+c²t^-21 on Mⁿ, where t₁ and t₂ are the positive real roots of （1.5）.     

Improvements on the Johnson bound for Reed-Solomon codes

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than , there can be at most O(n²) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k<αn for any constant 0<α<1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius (for any c>0) there can be at most number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the bound is not sacrosanct for such a high rate.We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds . We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

A description of continued fraction expansions of quadratic surds represented by polynomials

The principal thrust of this investigation is to provide families of quadratic polynomials , where e_k²−f_k²C=n (for any given nonzero integer n) satisfying the property that for any , the period length of the simple continued fraction expansion of is constant for fixed k and lim_k→∞?_k=∞. This generalizes, and completes, numerous results in the literature, where the primary focus was upon |n|=1, including the work of this author, and coauthors, in Mollin (Far East J. Math. Sci. Special Vol. 1998, Part III, 257-293; Serdica Math. J. 27 (2001) 317) Mollin and Cheng (Math. Rep. Acad. Sci. Canada 24 (2002) 102; Internat Math J 2 (2002) 951) and Mollin et al. (JP J. Algebra Number Theory Appl. 2 (2002) 47).     

Preemptive scheduling of equal-length jobs to maximize weighted throughput

We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput. In Graham's notation this problem is described as . We provide an O(n⁴)-time algorithm, improving the previous bound of O(n¹⁰).     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Precise rates in the law of logarithm for the moment convergence of i.i.d. random variables

Let be a sequence of i.i.d. random variables with EX=0 and EX²=σ²<∞. Set , Mn=maxk?n|Sk|, n?1. Let r>1, then we obtain

     

On the complexity of computing treelength

We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007) [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most k is NP-complete for every fixed k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than . Additionally, we show that treelength can be computed in time O^∗(1.7549ⁿ) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.