Combinatorics

In recent years P. C. Hammer's problem of determining a convex body from its 'X-ray pictures' was investigated by Gardner and McMullen [4], Gardner [3], Falconer and Volcic . An earlier result is due to Giering . An X-ray picture of a convex body in a direction may be identified with its Steiner symmetral in that direction. Some of these papers consider X-ray pictures taken from points not on the line at infinity, but here we are not concerned with that situation. Gardner and McMullen proved that there exist four directions such that the corresponding X-ray pictures distinguish between all convex bodies, and that no three directions can do this. Giering proved that, given a plane convex body K, there exist three directions depending on K, such that the corresponding X-ray pictures distinguish K from any other convex body. He has also shown that two directions are in general not enough. Convex bodies with the same X-ray pictures as a given one were called 'ghosts' in , in analogy with the ghost densities from computerized tomography .

Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal language L ⊆ Σ * , the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) ∈ L. Here l(p) denotes the unique word obtained by concatenating the Σ-labels of the edges along the path p. The main contributions of this paper include the following: (1) We show that the formal-language-constrained shortest path problem is solvable efficiently in polynomial time when L is restricted to be a context-free language (CFL). When L is specified as a regular language we provide algorithms with improved space and time bounds. (2) In contrast, we show that the problem of finding a simple path between a source and a given destination is NP-hard, even when L is restricted to fixed simple regular languages and to very simple classes of graphs (e.g., complete grids). (3) For the class of treewidth-bounded graphs, we show that (i) the problem of finding a regular-language-constrained simple path between source and destination is solvable in polynomial time and (ii) the extension to finding CFL-constrained simple paths is NP-complete. Our results extend the previous results in [SIAM

We study a class of discrete dynamical systems that is motivated by the generic structure of simulations. The systems consist of the following data: (a) a ®nite graph Y with vertex set f1Y F F F Y ng where each vertex has a binary state, (b) functions p i X F n 2 3 F n 2 and (c) an update ordering p. The functions p i update the binary state of vertex i as a function of the state of vertex i and its Y-neighbors and leave the states of all other vertices ®xed. The update ordering is a permutation of the Y-vertices. By composing the functions p i in the order given by p one obtains the sequential dynamical system (SDS DS): We derive a decomposition result, characterize invertible SDS DS and study ®xed points. In particular we analyse how many dierent SDS D S that can be obtained by reordering a given multiset of update functions and give a criterion for when one can derive concentration results on this number. Finally, some speci®c SDS DS are investigated.

The Vassiliev conjecture states that the Vassiliev invariants are dense in the space of all numerical link invariants in the sense that any link invariant is a pointwise limit of Vassiliev invariants. In this article, we prove that the Vassiliev conjecture holds in the case of the coefficients of the HOMFLY and the Kauffman polynomials. Contents 1 Reducing the problem: the weak Vassiliev conjecture 2 2 Approximation of the coefficients of the HOMFLYPT polynomial by Vassiliev invariants 3 2.1 Notations .

Khovanov homology for knots has generated a flurry of activity in the topology community. This paper studies the Khovanov type cohomology for graphs with a special attention to torsion. When the underlying algebra is Z[x]/(x 2), we determine precisely those graphs whose cohomology contains torsion. For a large class of algebras, we show that torsion often occurs. Our investigation of torsion led to other related general results. Our computation could potentially be used to predict the Khovanov-Rozansky sl(m) homology of knots (in particular (2,n) torus knot). We also predict that our work is

We present a novel topological proof of Goldbachs Conjecture, which states that every even integer greater than 2 can be expressed as the sum of two primes. By constructing a Prime Resonance Manifold M P , we define a resonance structure induced by prime numbers, where even integers arise as intersections of prime resonance trajectories. The proof leverages the dense tessellation of the manifold by prime resonance domains and entropydriven dynamics to ensure the existence of such intersections. TikZ illustrations visualize the manifold, resonance domains, and trajectory intersections, providing intuitive insight into the topological framework.

The LYM inequality (Lubell, Yamamoto, Meshalkin) is a generalization of Sperner's theorem for antichains. Kleitman and Harper independently proved that the LYM inequality and the normalized matching property (or local LYM inequality) are equivalent. Many contributions have been proposed to sharpen the LYM inequality. Noticeably, Ahlswede and Zhang lifted the LYM inequality to an identity, called the AZ identity. Thus, one expects that the same sharpening of the local LYM inequality is equivalent to the AZ identity. In this paper, we introduce a local LYM identity which sharpens the local LYM inequality and prove that it is equivalent to the AZ identity. The local LYM identity shows local relationships between components in the AZ identity.

A simple path cover of a graph G is a collection ψ of paths in G such that every edge of G is in exactly one path in ψ and any two paths in ψ have at most one vertex in common. More generally, for any integer k ≥ 1, a Smarandache path k-cover of a graph G is a collection ψ of paths in G such that each edge of G is in at least one path of ψ and two paths of ψ have at most k vertices in common. Thus if k = 1 and every edge of G is in exactly one path in ψ, then a Smarandache path k-cover of G is a simple path cover of G. The minimum cardinality of a simple path cover of G is called the simple path covering number of G and is denoted by πs(G). In this paper we initiate a study of this parameter.

A decomposition of a graph 𝐺 is a collection 𝜓 of edge-disjoint subgraphs 𝐻 1 , 𝐻 2 , . . . , 𝐻 𝑟 of 𝐺 such that every edge of 𝐺 belongs to exactly one 𝐻 𝑖 . If each 𝐻 𝑖 is a path or a cycle in 𝐺, then 𝜓 is called a path decomposition of 𝐺. If each 𝐻 𝑖 is a path in 𝐺, then 𝜓 is called an acyclic path decomposition of 𝐺. The minimum cardinality of a path decomposition (acyclic path decomposition) of 𝐺 is called the path decomposition number (acyclic path decomposition number) of 𝐺 and is denoted by 𝜋(𝐺) (𝜋 𝑎 (𝐺)). In this paper we initiate a study of the parameter 𝜋 and determine the value of 𝜋 for some standard graphs. Further, we obtain some bounds for 𝜋 and characterize graphs attaining the bounds. We also prove that the difference between the parameters 𝜋 and 𝜋 𝑎 can be made arbitrarily large.

A decomposition of a graph G is a collection ψ = {H 1 , H 2 , . . . , H k } of subgraphs of G such that every edge of G belongs to exactly one H i . The decomposition ψ is called a path decomposition of G if each H i is a path in G. Several studies have been undertaken on path decompositions by imposing certain conditions on the paths considered in the decomposition of the graph where the primary objective is to obtain the minimum number of paths required for a certain type of decomposition for a given graph. A path decomposition ψ such that the paths in ψ are induced as well as of same parity is defined as an equiparity induced path decomposition. The minimum number of paths in such a decomposition of a graph G is called the equiparity induced path decomposition number of G and is denoted by π pi (G). In this paper we determine the value of π pi for trees of even size.

Let P1 and P2 be graphical properties. A Smarandachely (P1, P2)- decomposition of a graph G is a decomposition of G into subgraphs G1,G2, � � � ,Gl ∈ P such that Gi ∈ P1 or Gi 6∈ P2 for integers 1 ≤ i ≤ l. Particularly, if P2 = ∅, i.e., a usual decomposition of a graph, is a collection of its subgraphs whose union equals the edge set of the graph. In this paper we introduce and initiate a study of a new variation of decom- position namely equiparity induced path decomposition of a graph which is defined to be a decomposition in which all the members are induced paths having same parity.

In a graph G = (V, E)(not necessarily be connected) an independent set S ⊆ V is said to be an outer connected independent set if ω(G -S) ≤ ω(G), where ω(G) is the number of components in G. The maximum cardinality of an outer connected independent set is called the outer connected independence number and it is denoted by I oc (G). This concept was introduced in [3]. This paper examine the effect of I oc when G is modified by deleting an edge.

Let G be a non-trivial, simple, finite, connected and undirected graph of order n and size m. An induced acyclic graphoidal decomposition (IAGD) of G is a collection ψ of non-trivial and internally disjoint induced paths in G such that each edge of G lies in exactly one path of ψ. For a labeling f : V → {1, 2, 3, . . . ,n}, let ↑ Gf be the directed graph obtained by orienting the edges uv of G from u to v, provided f(u) < f(v). If the set ψ

Let be a nontrivial, simple, finite, connected, and undirected graph. A graphoidal decomposition (GD) of is a collection of nontrivial paths and cycles in that are internally disjoint such that every edge of lies in exactly one member of . By restricting the members of a GD to be induced, the concept of induced graphoidal decomposition (IGD) of a graph has been defined. The minimum cardinality of an IGD of a graph is called the induced graphoidal decomposition number and is denoted by (). An IGD of without any cycles is called an induced acyclic graphoidal decomposition (IAGD) of , and the minimum cardinality of an IAGD of is called the induced acyclic graphoidal decomposition number of , denoted by (). In this paper we determine the value of () and () when is a product graph, the factors being paths/cycles.

A subsetSof the vertex setV(G)of a graphGis called an isolate set if the subgraph induced byShas an isolated vertex. The subsetSis called an isolate dominating set if it is both isolate and dominating. Also,Sis called an isolate irredundant set if it is both isolate and irredundant. In this paper, we establish a chain connecting various isolate parameters with the existing domination parameters and discuss equality among the parameters in the extended chain.

There are plenty of topological indices used in chemistry to study the chemical behavior and physical properties of molecular graphs. In the literature, several results are computed for degree based topological indices like “first Zagreb index, second Zagreb index, modified second Zagreb index, generalized Randić index, inverse Randić index, symmetric sum division index, harmonic index, inverse sum index, augmented Zagreb index”. In this paper, we have investigated the aforesaid degree based topological indices for Hanoi graph and generalized wheel graph with the help of M-polynomial.

For a positive integer n > 1, the unitary addition Cayley graph G n is the graph whose vertex set is For G n the independence number, chromatic number, edge chromatic number, diameter, vertex connectivity, edge connectivity and perfectness are determined.

In a graph, diametral path is shortest path between two vertices which has length equal to diameter of the graph. Number of diametral paths plays an important role in computer science and civil engineering. In this paper, we introduce the concept of extended transformation graphs. There are 64 extended transformation graphs. We obtain number of diametral paths in some of the extended transformation graphs and we also study the semi-complete property of these extended transformation graphs. Further, a program is given for obtaining number of diametral paths.

The identity linking the Tutte polynomial with the Potts model on a graph implies the existence of a decomposition resembling that previously obtained for the chromatic polynomial. Specifically, let {G n } be a family of bracelets in which the base graph has b vertices. Then the Tutte polynomial of G n can be written as a sum of terms, one for each partition π of a non-negative integer ≤ b: The matrices N π (x, y) are (essentially) the constituents of a 'Potts transfer matrix', and their 'multiplicities' m π (x, y) are obtained by substituting k = (x -1)(y -1) in the expressions m π (k) previously obtained in the chromatic case. As an illustration, we shall give explicit calculations for bracelets in which b is small, obtaining (for example) an exact formulae for the Tutte polynomials of the quartic plane ladders.

or visit the DOI to the publisher's website. • The final author version and the galley proof are versions of the publication after peer review. • The final published version features the final layout of the paper including the volume, issue and page numbers. Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. • Users may download and print one copy of any publication from the public portal for the purpose of private study or research. • You may not further distribute the material or use it for any profit-making activity or commercial gain • You may freely distribute the URL identifying the publication in the public portal. If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the "Taverne" license above, please follow below link for the End User

Graphs are useful for analysing the structure models in computer science, operations research, and sociology. The word metric dimension is the basis of the distance function, which has a symmetric property. Moreover, finding the resolving set of a graph is NP-complete, and the possibilities of finding the resolving set are reduced due to the symmetric behaviour of the graph. In this paper, we introduce the idea of the edge-multiset dimension of graphs. A representation of an edge is defined as the multiset of distances between it and the vertices of a set, B ⊆ V(Γ). If the representation of two different edges is unequal, then B is an edge-multiset resolving a set of Γ. The least possible cardinality of the edge-multiset resolving a set is referred to as the edge-multiset dimension of Γ. This article presents preliminary results, special conditions, and bounds on the edge-multiset dimension of certain graphs. This research provides new insights into structure models in computer science, operations research, and sociology. They could have implications for developing computer algorithms, aircraft scheduling, and species movement between regions.

Graphs are useful for analysing the structure models in computer science, operations research, and sociology. The word metric dimension is the basis of the distance function, which has a symmetric property. Moreover, finding the resolving set of a graph is NP-complete, and the possibilities of finding the resolving set are reduced due to the symmetric behaviour of the graph. In this paper, we introduce the idea of the edge-multiset dimension of graphs. A representation of an edge is defined as the multiset of distances between it and the vertices of a set, B⊆V(Γ). If the representation of two different edges is unequal, then B is an edge-multiset resolving a set of Γ. The least possible cardinality of the edge-multiset resolving a set is referred to as the edge-multiset dimension of Γ. This article presents preliminary results, special conditions, and bounds on the edge-multiset dimension of certain graphs. This research provides new insights into structure models in computer scienc...

We prove an existence result/or strong solutions to a class o//unctional di//erential equations o/the/orm u'(t) + a~(n(t)) e ~(t, u(t), u~), o < t < z u(s) = v(s) , -T <_ s ~ o , where 2~: [0, T] • D(O~) • Coe([--v, 0]; H) ~ tt satisfies a certain demiclosedness condition, 0 while v e Ca~([--z, 0]; H), v(0)e JO(~0) and ~H~q~O(v(s))Heds < -~ po. l. -Introduction. Throughout this paper H is a real ttilbert space with inner product (., .) and norm I['11, ~0: H -+ [0, q-~] is ~ proper 1.s.c. convex function and ~ is the subdifferential of ~. If [a, b] is an interval in R, then Ce~([a, b]; H) denotes the subset of all functions v belonging to C([a, b] ; H) and satisfying v(t) ~ D(~9~ ) a.e. for t e (a, b). We emphasize that in all that follows Ce~([a, b]; H) is endowed with the sup. norm topology of C([a, b]; H). Let ~ ~ 0 and T ~ 0 be two given constants. We recall that if ue Ca~([--~, T]; H) and te [0, T], then u~: [--T, 0] -->H is defined by u,(s) := u(t + s), for every se[--~, 0]. Obviously, whenever ~e Car % T]; H) and te [0, T], u~ belongs to C~([--% 0]; H). Let F: [0, T]•215 % 0]; H) -->H be a given function, and let us (*) Entrata in Redazione il 14 aprile 1987. (**) Research done while the second author was a C.N.R. visiting professor at the University of Trieste, Italy.

We construct an explicit diagonal ∆ P on the permutahedra P. Related diagonals on the multiplihedra J and the associahedra K are induced by Tonks' projection P → K [19] and its factorization through J. We introduce the notion of a permutahedral set Z and lift ∆ P to a diagonal on Z. We show that the double cobar construction Ω 2 C * (X) is a permutahedral set; consequently ∆ P lifts to a diagonal on Ω 2 C * (X). Finally, we apply the diagonal on K to define the tensor product of A ∞ -(co)algebras in maximal generality.

We complete the construction of the biassociahedra KK, construct the free matrad H∞, realize H∞ as the cellular chains of KK, and define an A∞-bialgebra as an algebra over H∞. We construct the bimultiplihedra JJ, construct the relative free matrad rH∞ as a H∞-bimodule, realize rH∞ as the cellular chains of JJ, and define a morphism of A∞-bialgebras as a bimodule over H∞. We prove that the homology of every A∞-bialgebra over a commutative ring with unity admits an induced A∞-bialgebra structure. We extend the Bott-Samelson isomorphism to an isomorphism of A∞-bialgebras and determine the A∞-bialgebra structure of H * (ΩΣX; Q). For each n ≥ 2, we construct a space Xn and identify an induced nontrivial A∞-bialgebra operation ω n 2 : H * (ΩXn; Z 2 ) ⊗2 → H * (ΩXn; Z 2 ) ⊗n .

Tác giả chính của tài liệu này là Lisa M. Benson, thuộc Dakota Consulting, có hợp đồng với Văn phòng Ðiều phối Tiêu chuẩn của NIST. Nhân viên của Văn phòng Điều phối Tiêu chuẩn của NIST có thêm hướng dẫn, nghiên cứu ban đầu và rà soát tài liệu, trong đó có: Mary Donaldson và Karen Reczek. Tài liệu cũng nhận được sự hỗ trợ quý giá của các chuyên gia đầy kiến thức thuộc Ủy ban An toàn Sản phẩm Tiêu dùng và Ủy ban Thương mại Liên bang, là những người đã góp ý cho tài liệu và rà soát kỹ lưỡng. Các nhà rà soát của Ủy ban An toàn Sản phẩm Tiêu dùng là Patty Edwards và Arlene Flecha Castro. Các nhà rà soát của Ủy ban Thương mại Liên bang là Steve Ecklund và Robert Frisby.

In this note, we introduce the energy method for constructing the length of addition chains leading to $2^n-1$. This method is a generalization of the Brauer method. Using this method, we show that the conjecture is true for all addition chains with "low" energy.

i-1 u (2i-1) , . . . , (-1) n-1 u (2n-1) ), where n ≥ 2 and f ∈ C([0, 1] × R n+1 + , R + ) (R + := [0, ∞)) depends on u and all derivatives of odd orders. Our main hypotheses on f are formulated in terms of the linear function g(x) := x 1 + 2 P n+1 i=2 x i . We use fixed point index theory to establish our main results, based on a priori estimates achieved by utilizing some integral identities and an integral inequality. Finally, we apply our main results to establish the existence, multiplicity and uniqueness of positive symmetric solutions for a Lidostone problem involving an open question posed by P. W. Eloe in 2000.

The circuit complexity class DLOGTIME-uniform AC 0 is known to be a modest subclass of DLOGTIME-uniform TC 0 . The weakness of AC 0 is caused by the fact that AC 0 is not closed under restricting AC 0 -computable queries into simple subsequences of the input. Analogously, in descriptive complexity, the logics corresponding to DLOGTIME-uniform AC 0 do not have the relativization property and hence they are not regular. This weakness of DLOGTIME-uniform AC 0 has been elaborated in the line of research on the Crane Beach Conjecture. The conjecture (which was refuted by Barrington, Immerman, Lautemann, Schweikardt and Thérien in [BIL + 05]) was that if a language L has a neutral letter, then L can be defined in FOA, first-order logic with the collection of all numerical built-in relations A, if and only if L can be already defined in FO ≤ . In the first part of this article we consider logics in the range of AC 0 and TC 0 . First we formulate a combinatorial criterion for a cardinality quantifier CS implying that all languages in DLOGTIME-uniform TC 0 can be defined in FO ≤ (CS). For instance, this criterion is satisfied by CS if S is the range of some polynomial with positive integer coefficients of degree at least two. In the second part of the paper we first adapt the key properties of abstract logics to accommodate built-in relations. Then we define the regular interior R-int(L) and regular closure R-cl(L), of a logic L, and show that the Crane Beach Conjecture can be interpreted as a statement concerning R-int (FOB). By extending the results of [BIL + 05], we show that if B = {+}, or B contains only unary relations besides ≤, then R-int(FOB) ≡ FO ≤ . In contrast, our results imply that if B contains ≤ and the range of a polynomial of degree at least two, then R-cl(FOB) includes all languages in DLOGTIME-uniform TC 0 .

We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

Dans cet article, nous présenterons les travaux préliminaires menés sur l'utilisation d'algorithmes d'approximation en Programmation Par Contraintes afin d'améliorer le calcul de bornes lors de la résolution de problèmes d'optimisation sous contraintes. L'objectif de nos travaux est d'étudier plus particulièrement quels algorithmes d'approximation présentent suffisamment de flexibilité pour être utilisés en Programmation Par Contraintes, et comment les utiliser au sein d'un propagateur qui mettra à jour les bornes de la variable-objectif à chaque noeud de l'espace de recherche. Enfin l'idée sera d'appliquer cette approche à plusieurs familles de problèmes d'optimisation afin d'en extraire une généralisation.

Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforeseen event occurs. We focus on the complexity of finding an (a, b)-supermatch. An (a, b)-supermatch is defined as a stable matching in which if any a (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those a men/women and also the partners of at most b others. In order to show deciding if there exists an (a, b)-supermatch is N P-complete, we first introduce a SAT formulation that is N P-complete by using Schaefer's Dichotomy Theorem. Then, we show the equivalence between the SAT formulation and finding a (1, 1)-supermatch on a specific family of instances.

Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforeseen event occurs. We focus on the complexity of finding an (a, b)-supermatch. An (a, b)-supermatch is defined as a stable matching in which if any a (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those a men/women and also the partners of at most b others. In order to show deciding if there exists an (a, b)-supermatch is N P-complete, we first introduce a SAT formulation that is N P-complete by using Schaefer's Dichotomy Theorem. Then, we show the equivalence between the SAT formulation and finding a (1, 1)-supermatch on a specific family of instances.

The paper deals with the uniformly elliptic equation (aiJ(z)u=,)=, = f(z) in an unbounded domain f2 C R n and its solution u(x) that satisfies the homogeneous Neumann condition. The function f has a compact support. The domain f2 has the following structure: assume that {r~ } is an increasing sequence of positive numbers, hm = r,~+l -r~, and the ratio hm+t/hr~ lies between positive constants C1 and C2. The intersection off2 with the spherical layer between the spheres of radius r,, and r~+l with center at the origin satisfies a certain inequality of isoperimetric type. It is shown in this paper that the set of solutions splits up into three classes: (i) the solutions for which lim u(z) = ee and lira U(z) = oe; I r l -* oo M ..+ oo moreover, it is shown that these limits are attained with nearly the same speed (if C1/C2 = 1, then the speed is not less than the exponential one); (ii) the solutions for each of which a constant C exists such that lim u(x) = C and u(z) -C changes its sign for large tzl; here, the convergence to C is rapid (for I=1-~oo C1/C2 = 1 this convergence is not slower than the exponential one); (iii) the solutions that do not change their sign for large I=1 and increase or decrease to +co or -oc, respectively, with low speed (for C1/C2 = 1 with a linear speed) (one exception is possible here: a slow convergence to a constant). Bibliography: 7 titles.

The well-known notion of dimension for partial orders by Dushnik and Miller allows to quantify the degree of incomparability and, thus, is regarded as a measure of complexity for partial orders. However, despite its usefulness, its definition is somewhat disconnected from the geometrical idea of dimension, where, essentially, the number of dimensions indicates how many real lines are required to represent the underlying partially ordered set. Here, we introduce a variation of the Dushnik-Miller notion of dimension that is closer to geometry, the Debreu dimension, and show the following main results: (i) how to construct its building blocks under some countability restrictions, (ii) its relation to other notions of dimension in the literature, and (iii), as an application of the above, we improve on the classification of preordered spaces through real-valued monotones.

For [Formula: see text], define [Formula: see text] as the set of integers [Formula: see text]. Given an integer [Formula: see text] and a string [Formula: see text] of length [Formula: see text] over [Formula: see text], we count the number of times that each one of the [Formula: see text] distinct strings of length [Formula: see text] over [Formula: see text] occurs as a subsequence of [Formula: see text]. Our algorithm makes only one scan of [Formula: see text] and solves the problem in time complexity [Formula: see text] and space complexity [Formula: see text]. These are very close to best possible.

Let k be a field of characteristic zero. For every smooth, projective k-variety Y of dimension n which admits a connected, proper morphism f : Y → S of relative dimension one, we construct idempotent correspondences (projectors )), then we can construct a projector π 2 (Y ) which lifts the second Künneth component of the diagonal of Y . Using this we prove that many smooth projective 3-folds X over k admit a Chow-Künneth decomposition ∆ = p 0 + ... We say that X has a Chow-Künneth decomposition, if there exist projectors p 0 , p 1 , ..., p 2d in CH d (X × X) ⊗ Q such that the following properties hold: (1) (2) ∆ = p i . (3) In étale cohomology the p i induce the (2di, i)-th Künneth component of the diagonal. We say that X has a Murre decomposition, if additionally the following properties hold: (4) p 0 , ..., p j-1 and p 2j+1 , .., p 2d act trivially on CH j (X) ⊗ Q. (5 a closed subset of dimension and p d-= p tr d+ for all . Conjecture (J. Murre). Every smooth projective variety has a Murre decomposition. Parts of (1)-(6) have been proved for curves [K], [M], surfaces [Mu2], products of a curve and a surface [Mu1], uniruled 3-folds [dAMS], elliptic modular 3-folds [GM],

Lee discrepancy has been employed to measure the uniformity of fractional factorials. In this paper, we further study the statistical justification of Lee discrepancy on asymmetrical factorials. We will give an expression of the Lee discrepancy of asymmetrical factorials with two-and three-levels in terms of quadric form, present a connection between Lee discrepancy, orthogonality and minimum moment aberration, and obtain a lower bound of Lee discrepancy of asymmetrical factorials with two-and three-levels.

In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated α-fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any α centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the {0, L}-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming α is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem.

The traveling salesman problem (TSP) is the problem of finding a shortest Hamiltonian circuit or path in a given weighted graph. This problem has been studied in numerous variants, and linear programming has played an important role in the design of approximation algorithms for these problems. In this thesis, we study two versions of the traveling salesman problem and present approximation algorithms for them based on the Held-Karp relaxation. We first investigate the s-t path TSP. Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem; this asymptotically tight bound had remained the best approximation ratio known until now. We surpass this 20-year-old barrier by presenting a deterministic 1+ √ 5