Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

On double bound graphs and forbidden subposets

For a poset P=(X,≤_P), the double bound graph (DB-graph) of P is the graph DB(P)=(X,E_DB(P)), where xy∈E_DB(P) if and only if x≠y and there exist n,m∈X such that n≤_Px,y≤_Pm. We obtain that for a subposet Q of a poset P,Q is an (n, m)-subposet of P if and only if DB(Q) is an induced subgraph DB(P). Using this result, we show some characterizations of split double bound graphs, threshold double bound graphs and difference double bound graphs in terms of (n, m)-subposets and double canonical posets.     

On Polygons Enclosing Point Sets II

Let R and B be disjoint point sets such that R ∪ B is in general position. We say that B encloses by R if there is a simple polygon P with vertex set B such that all the elements in R belong to the interior of P. In this paper we prove that if the vertices of the convex hull of R ∪ B belong to B, and |R| ≤ |Conv(B)| − 1 then B encloses R. The bound is tight. This improves on results of a previous paper in which it was proved that if |R| ≤ 56 |Conv(B)| then B encloses R. To obtain our result we prove the next result which is interesting on its own right: Let P be a convex polygon with n vertices p ₁ , ... , p _n and S a set of m points contained in the interior of P, m ≤ n − 1. Then there is a convex decomposition {P ₁ , ... , P _n } of P such that all points from S lie on the boundaries of P ₁ , ... , P _n , and each P _i contains a whole edge of P on its boundary. F. Hurtado partially supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692. C. Merino supported by CONACYT of Mexico, Proyecto 43098. J. Urrutia supported by CONACYT of Mexico, Proyecto SEP-2004-Co1-45876, and MCYT BFM2003-04062. I. Ventura partially supported by Project MCYT BFM2003-04062.     

Computing Orbits of the Automorphism Group of the Subsequence Poset B m,n

Let B _m,n denote the set of all words obtained from the cyclic word of length n on an alphabet of m letters in by deleting on all possible ways and their natural order. In [Order, 16: 179–194, 1999] Burosch et al. computed the automorphism group of the poset B _m,n . In this paper, we apply this result to obtain all of orbits of the natural action of Aut(B _m,n ) on B _m,n .     

Characterization of a class of triangle-free graphs with a certain adjacency property

Let m and n be nonnegative integers. Denote by P(m,n) the set of all triangle-free graphs G such that for any independent m-subset M and any n-subset N of V(G) with M ∩ N = Ø, there exists a unique vertex of G that is adjacent to each vertex in M and nonadjacent to any vertex in N. We prove that if m ? 2 and n ? 1, then P(m,n) = Ø whenever m ? n, and P(m,n) = {K_m,n+1} whenever m > n. We also have P(1,1) = {C₅} and P(1,n) = Ø for n ? 2. In the degenerate cases, the class P(0,n) is completely determined, whereas the class P(m,0), which is most interesting, being rich in graphs, is partially determined.     

Maximizing the distance between center,centroid and characteristic set of a tree

Consider a tree P_n-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2,?…?,n-g] vertices by adding g pendant vertices to the pendant vertex n-g. We prove that over all trees on n?≥?5 vertices, the distance between center and characteristic set, centroid and characteristic set, and center and centroid is maximized by trees of the form P_n-g,g , 2?≤?g?≤?n-3. For n≥ 5, we also supply the precise location of the characteristic set of the tree P_n-g,g , 2?≤?g?≤?n-3.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

A bound for the topological entropy of homeomorphisms of a punctured two-dimensional disk

We consider homeomorphisms ƒ of a punctured 2-disk D ² \ P, where P is a finite set of interior points of D ², which leave the boundary points fixed. Any such homeomorphism induces an automorphism ƒ _* of the fundamental group of D ² \ P. Moreover, to each homeomorphism ƒ, a matrix B _ƒ (t) from GL(n, ℤ[t, t ⁻¹]) can be assigned by using the well-known Burau representation. The purpose of this paper is to find a nontrivial lower bound for the topological entropy of ƒ. First, we consider the lower bound for the entropy found by R. Bowen by using the growth rate of the induced automorphism ƒ _*. Then we analyze the argument of B. Kolev, who obtained a lower bound for the topological entropy by using the spectral radius of the matrix B _ƒ (t), where t ∈ ℂ, and slightly improve his result. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 5, pp. 47–55, 2005.     

On Poset Boolean Algebras

Let (P,≤) be a partially ordered set. The poset Boolean algebra of P, denoted F(P), is defined as follows: The set of generators of F(P) is {x _p  : p∈P}, and the set of relations is {x _p ⋅x _q =x _p  : p≤q}. We say that a Boolean algebra B is well-generated, if B has a sublattice G such that G generates B and (G,≤ ^B |G) is well-founded. A well-generated algebra is superatomic. THEOREM 1. Let (P,≤) be a partially ordered set. The following are equivalent. (i) P does not contain an infinite set of pairwise incomparable elements, and P does not contain a subset isomorphic to the chain of rational numbers, (ii) F(P) is superatomic, (iii) F(P) is well-generated. The equivalence (i) ⇔ (ii) is due to M. Pouzet. A partially ordered set W is well-ordered, if W does not contain a strictly decreasing infinite sequence, and W does not contain an infinite set of pairwise incomparable elements. THEOREM 2. Let F(P) be a superatomic poset algebra. Then there are a well-ordered set W and a subalgebra B of F(W), such that F(P) is a homomorphic image of B. This is similar but weaker than the fact that every interval algebra of a scattered chain is embeddable in an ordinal algebra. Remember that an interval algebra is a special case of a poset algebra. This revised version was published online in June 2006 with corrections to the Cover Date.     

Anti‐magic graphs via the Combinatorial NullStellenSatz

An antimagic labeling of a graph with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it has an antimagic labeling. In [ 10 ], Ringel conjectured that every simple connected graph, other than K₂, is antimagic. We prove several special cases and variants of this conjecture. Our main tool is the Combinatorial NullStellenSatz (cf. [ 1 ]). © 2005 Wiley Periodicals, Inc. J Graph Theory     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Equipartite polytopes

A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V ₁ and V ₂, there is an isometry of the polytope P that maps V ₁ onto V ₂. We prove that an equipartite polytope in ℝ ^d can have at most 2d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ ^d . We conjecture that the list is complete.     

Note on upper bound graphs and forbidden subposets

In the upper bound graph of a poset P, the vertex set is V(P) and xy is an edge if there exists an m∈V(P) with x,y≤_Pm. We show some characterizations on split upper bound graphs, threshold upper bound graphs and difference upper bound graphs in terms of m-subposets and canonical posets.     

Random subgraphs of finite graphs: I. The scaling window under the triangle condition

We study random subgraphs of an arbitrary finite connected transitive graph ?? obtained by independently deleting edges with probability 1 ? p. Let V be the number of vertices in ??, and let Ω be their degree. We define the critical threshold p_c = p_c (??, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV^1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p_c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p_c. In particular, we show that the largest cluster inside a scaling window of size |p ? p_c| = Θ(Ω^?1V^?1/3) is of size Θ(V^2/3), while, below this scaling window, it is much smaller, of order O(?^?2 log(V?³)), with ? = Ω(p_c ? p). We also obtain an upper bound O(Ω(p ? p_c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p ? p_c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A note on Ramsey numbers for books

The book with n pages B_n is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B_m,B_n) is the smallest integer r such that either B_m ? G or B_n ? G for every graph G of order r. We prove that there exists a positive constant c such that r(B_m,B_n) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.     

How To Split Antichains In Infinite Posets*

A maximal antichain A of poset P splits if and only if there is a set B ⊂ A such that for each p ∈ P either b ≤ p for some b ∈ B or p ≤ c for some c ∈ A\B. The poset P is cut-free if and only if there are no x < y < z in P such that [x,z]_P = [x,y]_P ∪ [y,z]_P . By [1] every maximal antichain in a finite cut-free poset splits. Although this statement for infinite posets fails (see [2])) we prove here that if a maximal antichain in a cut-free poset “resembles” to a finite set then it splits. We also show that a version of this theorem is just equivalent to Axiom of Choice. We also investigate possible strengthening of the statements that “A does not split” and we could find a maximal strengthening. * This work was supported, in part, by Hungarian NSF, under contract Nos. T37846, T34702, T37758, AT 048 826, NK 62321. The second author was also supported by Bolyai Grant.     

On the distribution of binary search trees under the random permutation model

We study the distribution Q on the set B_n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B_n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over B_n and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.