Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.     

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d ⁺(x) and d ⁻(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d ⁺(x) = d ⁻(x) = p for all vertices x of D. A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Critical points for spread-out self-avoiding walk,percolation and the contact process above the upper critical dimensions

We consider self-avoiding walk and percolation in ^d, oriented percolation in ^d×₊, and the contact process in ^d, with p D(·) being the coupling function whose range is proportional to L. For percolation, for example, each bond is independently occupied with probability p D(y–x). The above models are known to exhibit a phase transition when the parameter p varies around a model-dependent critical point p_c. We investigate the value of p_c when d>6 for percolation and d>4 for the other models, and L1. We prove in a unified way that p_c=1+C(D)+O(L^–2d), where the universal term 1 is the mean-field critical value, and the model-dependent term C(D)=O(L^–d) is written explicitly in terms of the random walk transition probability D. We also use this result to prove that p_c=1+cL^–d+O(L^–d–1), where c is a model-dependent constant. Our proof is based on the lace expansion for each of these models.     

Distance connectivity in graphs and digraphs

Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c₂ ≤ … ≤ c_D, D > 3, as the values of its t-distance connectivities κ(2) = c₂, …, κ(D) = c_D. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

Directed distance in digraphs: Centers and medians

The directed distance d_D(u, v) from a vertex u to a vertex v in a strong digraph D is the length of a shortest (directed) u - v path in D. The eccentricity of a vertex v in D is the directed distance from v to a vertex furthest from v. The distance of a vertex v in D is the sum of the directed distances from v to the vertices of D. The center C(D) of D is the subdigraph induced by those vertices of minimum eccentricity, while the median M(D) of D is the subdigraph induced by those vertices of minimum distance. It is shown that for every two asymmetric digraphs D₁ and D₂, there exists a strong asymmetric digraph H such that C(H) ? D₁ and M(H) ? D₂, and where the directed distance from C(H) to M(H) and from M(H) to C(H) can be arbitrarily prescribed. Furthermore, if K is a nonempty asymmetric digraph isomorphic to an induced subdigraph of both D₁ and D₂, then there exists a strong asymmetric digraph F such that C(F) ? D₁, M(F) ? D₂ and C(F) ∩ M(F) ? K. © 1993 John Wiley & Sons, Inc.     

The number of pancyclic arcs in a k‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D, if it belongs to a cycle of length l, for all 3 ≤ l ≤ |V (D) |. Let p(D) denote the number of pancyclic arcs in a digraph D and let h(D) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D. Note that p(D) ≥ h(D). Moon showed that h(T) ≥ 3 for all strong non‐trivial tournaments, T, and Havet showed that h(T) ≥ 5 for all 2‐strong tournaments T. We will show that if T is a k‐strong tournament, with k ≥ 2, then p(T) ≥ 1/2, nk and h(T) ≥ (k + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α_k, such that p(T) ≥ α_k n, for all k‐strong tournaments, T, with k ≥ 2. Furthermore, the second results gives support for the conjecture h(T) ≥ 2k + 1, which was also stated by Havet. The previously best‐known bounds when k ≥ 2 were p(T) ≥ 2k + 3 and h(T) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

 Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ₄(G)=min{d(x ₁)+d(x ₂)+ d(x ₃)+d(x ₄) | {x ₁,…,x ₄} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ₄(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Degree-uniform lower bound on the weights of polynomials with given sign function

A Boolean function f: {0, 1} ⁿ → {0, 1} is called the sign function of an integer polynomial p of degree d in n variables if it is true that f(x) = 1 if and only if p(x) > 0. In this case the polynomial p is called a threshold gate of degree d for the function f. The weight of the threshold gate is the sum of the absolute values of the coefficients of p. For any n and d ≤ D ≤ $\frac{{\varepsilon n^{1/5} }} {{\log n}} $\frac{{\varepsilon n^{1/5} }} {{\log n}} we construct a function f such that there is a threshold gate of degree d for f, but any threshold gate for f of degree at most D has weight 2^{(dn)d /D4d} 2^{(\delta n)^d /D^{4d} } , where ɛ > 0 and δ > 0 are some constants. In particular, if D is constant, then any threshold gate of degree D for our function has weight 2^{W(nd )}2^{\Omega (n^d )} . Previously, functions with these properties have been known only for d = 1 (and arbitrary D) and for D = d. For constant d our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was 2^Ω(n). Our results can also be translated to the case of functions f: {−1, 1} ⁿ → {−1, 1}.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

The Directed Geodetic Structure of a Strong Digraph

By a ternary structure we mean an ordered pair (U ₀, T ₀), where U ₀is a finitenonempty set and T ₀is a ternary relation on U ₀. A ternary structure (U ₀, T ₀) is called here a directed geodetic structure if there exists a strong digraph Dwith the properties that V(D) = U ₀and T ₀ (u,v, w)if and only if d _D (u,v)+ d _D (v,w)= d _D (u, w) for all u, v, w U ₀, where d _Ddenotes the (directed) distance function in D. It is proved in this paper that there exists no sentence sof the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies s.