bluuebunny/crossref_metadata_2025_split huggingface dataset:
Coloring Clique‐free Graphs in Linear Expected Time
Authors: Prömel Hans Jürgen , Steger Angelika 
Published: May 2007

AbstractThis article presents a linear expected time algorithm to color every graph which does not contain a clique on l + 1 vertices as a subgraph with a minimal number of colors. This extends a result of Dyer and Frieze for l‐colorable graphs. For the proof we develop a new method which allows us to precisely estimate the number of graphs with certain structural properties.
Local Limit Theorems for Sums of Power Series Distributed Random Variables and for the Number of Components in Labelled Relational Structures
Authors: Mutafchiev Lyuben R. 
Published: May 2007

AbstractA Local limit theorem for the distribution of the number of components in random labelled relational structures of size n (e.g., a type of random graphs on n vertices, random permutations of n elements, etc.) is proved as n→∞. The case when the corresponding exponential generating functions diverge at their radii of convergence is considered.
A Canonical Ramsey Theorem
Authors: Eaton Nancy , Rödl Vojtěch 
Published: May 2007

AbstractSay a graph H selects a graph G if given any coloring of H, there will be a monochromatic induced copy of G in H or a completely multicolored copy of G in H. Denote by s(G) the minimum order of a graph that selects G and set s(n) = max {s(G): |G| = n}. Upper and lower bounds are given for this function. Also, consider the Folkman function fr(n) = max{min{|V(H)|: H → (G)1r}: |V(G)| = n}, where H → (G)1r indicates that H is vertex Ramsey to G, that is, any vertex coloring of H with r colors admits a monochromatic induced copy of G. The method used provides a better upper bound for this function than was previously known. As a tool, we establish a theorem for projective planes.
Markov chains on hypercubes: Spectral representations and several majorization relations
Authors: Karlin Samuel , Lindqvist Bo , Yao Yi‐Ching 
Published: May 2007

AbstractVarious Markov chains on hypercubes ℒ︁are considered and their spectral representations are presentend in terms of Kronecker products. Special attention is given to random walks on the graphs 𝒮(l = 1,n − 2), where the vertex set is ℒ︁ and two vertices are connected if and only if their Hamming distance is at most l. It is shown that λ(𝒮1)>λ(𝒮1)>λ(𝒮n−1)>λ(𝒮n),l=2,…,n−2, where λ (𝒮I) is the specturum of the random walk on 𝒮I, and > denotes the majorization ordering. A similar majorization relation is established for graphs V1 where two veritces are connected if and only if their Hamming distance is exactly l. Some applications to mean times of these random walks are given. © 1993 John Wiley & Sons, Inc.
How homogeneous can the last appearing pattern be?
Authors: Móri Tamás F. 
Published: May 2007

AbstractGiven a sequence of indepent, uniformly distributed random letters coming from a finite alphabet, we are interested in the word (pattern) which is the last to be observed for the first time among all words of length n. We derive anas. result on the homogeneity of this last appearing pattern as a corollary of a more general theorem. © 1993 John Wiley & Sons, Inc.
The size Ramsey number of trees with bounded degree
Authors: Ke Xin 
Published: May 2007

AbstractThe size Ramsey number r̂(G, H) of graphs G and H is the smallest integer r̂ such that there is a graph F with r̂ edges and if the edge set of F is red‐blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r̂(Tnd, Tnd) ⩽ c · d2 · n and c · n3 ⩽ r̂(Kn, Tnd) ⩽ c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.
Searching for losers
Authors: Grabner Peter J. 
Published: May 2007

AbstractWe investigate the following process: N people select b losers by flipping coins. The 0‐party continues until there are less than b losers; then the 1‐party has to find the other losers by the same process. The average time for this process is about long2 N, but this result requires rather advanced methods. Furthermore, the average size of a binary tree associated to this process and the average number of coin flippings are computed. The method used in this article can be used to give asympotical solutions of a special type of bivariate recurrences. © 1993 John Wiley & Sons, Inc.
Efficient generation of random nonsingular matrices
Authors: Randall Dana 
Published: May 2007

AbstractWe present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n2), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n2 + 3. (Over other finite fields we use n2 + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.
The effect of random restrictions on formula size
Authors: Impagliazzo Russell , Nisan Noam 
Published: May 2007

AbstractWe consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ϵn variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω(n1.5) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of ΩC(n2.5/logO(1)(n)) for a function in P. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O(ϵγ) franction of its original complexity, formagnified imageThis allows us to give an improved lower bound of Ω(n2.556…) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.
On boolean decision trees with faulty nodes
Authors: Kenyon Claire , King Valerie 
Published: May 2007

AbstractWe consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that iffcan be represented ink‐DNF form and inj‐CNF form, thenO(nlog(min(k, j)/q)) queries suffice to computefwith error probability less thanq, wherenis the number of input bits. © 1994 John Wiley & Sons, Inc.
An upper bound for the solvability probability of a random stable roommates instance
Authors: Pittel Boris G. , Irving Robert W. 
Published: May 2007

AbstractIt is well‐known that not all instances of the stable roommates problem admit a stable matching. Here we establish the first nontrivial upper bound on the limiting behavior of Pn, the probability that a random roommates instance of size n has a stable matching, namely, limn→∞ Pn⩽ e1/2/2 (=0.8244…). © 1994 John Wiley & Sons, Inc.
Trie size in a dynamic list structure
Authors: Louchard G. 
Published: May 2007

AbstractThis article considers a classical binary tree implementation of a set of keys: the trie. The trie size properties in a static environment are well known: The size is asymptotically Gaussian when the number of keys is large. In this article we analyze the trie in a dynamic environment, where the trie is allowed to grow and shrink in a probabilistic way. It appears that the trie size can be described by a stochastic process which is asymptotically Gaussian non‐Markovian. This also allows the complete asymptotic analysis of the trie size maximum and the trie size integrated cost. © 1994 John Wiley & Sons, Inc.
On the number of cycles of given length of a free word in several random permutations
Authors: Nica Alexandru 
Published: May 2007

AbstractLet w ≠ 1 be a free word in the symbols g1,…, gk and their inverses (i.e., an element of the free group Fk). For any s1,…, sk, in the group sn of all permutation of n objects, we denote by w(s1,…,sk) ϵ Sn the permutation obtained by replacing g1,…, gk with s1,…, sk in the expression of w. Let X (s1,…, sk) denote the number of cycles of length L of w(s1,…, sk). For fixed w and L, we show that X, viewed as a random variable on Snk, has (for n →∞) a Poisson‐type limit distribution, which can be computed precisely. © 1994 John Wiley & Sons, Inc.
On the genus of a random graph
Authors: Rödl Vojtěch , Thomas Robin 
Published: May 2007

AbstractLet p = p(n) be a function of n with 0<p<1. We consider the random graph model 𝒢(n, p); that is, the probability space of simple graphs with vertex‐set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p2(1 − p2) 𝒢 8(log n)4/n. then the (orientable) genus of a random graph in 𝒢(n, p) is (1 + o(1))pn2/12. We prove that for every integer i ⩾ 1, if n−i/(i + 1) «p «n−(i − 1)/i. then the genus of a random graph in 𝒢(n, p) is (1 + o(1))i/4(i + 2) pn2. If p = cn−(i−1)/o, where c is a constant, then the genus of a random graph in 𝒢(n, p) is (1 + o(1))g(i, c, n)pn2 for some function g(i, c, n) with 1/12 ⩽ g(i, c, n) ⩽ 1. but for i > 1 we were unable to compute this function.
Random I‐colorable graphs
Authors: Prömel Hans Jürgen , Steger Angelika 
Published: May 2007

AbstractIn this article we investigate properties of the class of all l‐colorable graphs on n vertices, where l = l(n) may depend on n. Let Gln denote a uniformly chosen element of this class, i.e., a random l‐colorable graph. For a random graph Gln we study in particular the property of being uniquely l‐colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l‐colorable graphs on n vertices with m = m(n) edges.
Constructions of permutation arrays for certain scheduling cost measures
Authors: Naor Joseph , Roth Ron M. 
Published: May 2007

AbstractConstructions of permutation arrays are presented that are optimal or nearly‐optimal with respect to two cost measures: the so‐called longest‐jump measure and the longest‐monotone‐greedy‐subsequence measure. These measures arise in the context of scheduling problems in asynchronous, shared memory, multiprocessor machines.
Randomized greedy matching. II
Authors: Aronson Jonathan , Dyer Martin , Frieze Alan , Suen Stephen 
Published: May 2007

AbstractWe consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.
On the Monte carlo boolean decision tree complexity of read‐once formulae
Authors: Santha Miklos 
Published: May 2007

AbstractIn the boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. We prove for a large class of read‐once formulae that this trivial speed‐up is the best that a Monte Carlo algorithm can achieve. For every formulaFbelonging to that class we show that the Monte Carlo complexity ofFwith two‐sided errorpis (1 − 2p)R(F), and with one‐sided errorpis (1 −p)R(F), whereR(F) denotes the Las Vegas complexity ofF. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analogous to the lower bound due to Saks and Wigderson on their Las Vegas complexity.
Large antichains in the partition lattice
Authors: Canfield E. R. , Harper L. H. 
Published: May 2007

AbstractConsider the partially ordered set of all partitions of an n‐element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. We show that the ratio of the size of the largest antichain to the size of the largest rank exceeds n1/35 for all n sufficiently large.
Convergence in homogeneous random graphs
Authors: Łuczak Tomasz , Shelah Saharon 
Published: May 2007

AbstractFor a sequence p̄ = (p(1), p(2), ‥ .), let G(n, p̄) denote the random graph with vertex set {1, 2, ‥ ., n} in which two vertices i, j are adjacent with probability p(|i − j|), independently for each pair. We study how the convergence of probabilities of first order properties of G(n, p̄), can be affected by the behaviour of p̄ and the strength of the language we use.
Geometric algorithms for the minimum cost assignment problem
Authors: Tokuyama Takeshi , Nakano Jun 
Published: May 2007

AbstractWe consider the minimum‐cost λ‐assignment problem, which is equivalent to the minimum‐weight one‐to‐many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ⩾ k), respectively. Formulating the problem geometrically, we given an O(kn + k2.5n0.5 log1.5 n) time randomized algorithm, which is better than the existing O(kn2 + n2 log n) time algorithm if n > k log k.
Improved boolean formulas for the Ramsey graphs
Authors: Savický Petr 
Published: May 2007

AbstractIn the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well‐known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd2 log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}n of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log2 d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.
On an anti‐Ramsey property of Ramanujan graphs
Authors: Haxell P. E. , Kohayakawa Y. 
Published: May 2007

AbstractIf G and H are graphs, we write G→ H (respectively, G→ TH) if for any proper edge‐coloring γ of G there is a subgraph H' ⊂ G of G isomorphic to H (respectively, isomorphic to a subdivision of H) such that γ is injective on E(H'). Let us write Cl for the cycle of length l. Spencer (cf. Erdös 10]) asked whether for any g ⩾ 3 there is a graph G = Gg such that (i) G has girth g(G) at least g and (ii) G→ TC3. Recently, Rödl and Tuza [22] answered this question in the affirmative by proving, using nonconstructive methods, a result that implies that, for any t ⩾ 1, there is a graph G = Gt of girth t + 2 such that G→ C2t+2. In particular, condition (ii) may be strengthened to (iii) G→ C𝓁 for some l = 𝓁(G). For G = Gt above 𝓁 = 𝓁(G) = 2t + 2 = 2g(G) − 2. Here, we show that suitable Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak [18] are explicit examples of graphs G = Gg satisfying (i) and (iii) above. For such graphs, 𝓁 = l(G) in (iii) may be taken to be roughly equal to (3/2)g(G), thus considerably improving the value 2g(G) − 2 given in the result of Rödl and Tuza. It is not known whether there are graphs G of arbitrarily large girth for which (iii) holds with 𝓁 = 𝓁(G) = g(G).
Upper bounds for the expected length of a longest common subsequence of two binary sequences
Authors: Dančík Vlado , Paterson Mike 
Published: May 2007

AbstractLet f(n) be the expected length of a longest common subsequence of two random binary sequences of length n. It is known that the limit γ = limn→ ∞ n−1 f(n) exists. Improved upper bounds for γ are given using a new method.
Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
Authors: Alon Noga , Frieze Alan , Welsh Dominic 
Published: May 2007

AbstractThe Tutte‐Gröthendieck polynomial T(G; x, y) of a graph G encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the (x, y) plane give the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper k‐colorings, the (all terminal) reliability probability of the graph, and various other invariants the exact computation of each of which is well known to be #P‐hard. Here we develop a general technique that supplies fully polynomial randomised approximation schemes for approximating the value of T(G; x, y) for any dense graph G, that is, any graph on n vertices whose minimum.
The strong convergence of maximal degrees in uniform random recursive trees and dags
Authors: Devroye Luc , Lu Jiang 
Published: May 2007

AbstractWe show that the maximal degree in a uniform random recursive tree is almost surely (1 + o(1)) log2n. A random directed acyclic graph on n nodes is defined by connecting the ith node for each i > m with r of its predecessors uniformly and at random. The maximal degree is shown to be almost surely (1 + o(1))log1+1/rn.
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Authors: Krajíček Jan , Pudlák Pavel , Woods Alan 
Published: May 2007

AbstractWe prove lower bounds of the form exp(nε d), εd > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.
Perfect matchings in random s‐uniform hypergraphs
Authors: Frieze Alan , Janson Svante 
Published: May 2007

AbstractLet E = {X1, X2…, Xm} where the Xi ⊆ V for 1 ≤ i ≤ m are distinct. The hypergraph G = (V, E) is said to be s‐uniform if |X1| = s for 1 ≤ i ≤ m. A set of edges M = {Xi : i ϵ I} is a perfect matching if (i) i ≠ j ϵ I implies Xi ∩ Xi = 0, and (ii) ∪iϵI Xi = V.In this article we consider the question of whether a random s‐uniform hypergraph contains a perfect matching. Let s ≥ 3 be fixed and m/n4/3 → ∞. We show that an s‐uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n3/2 → ∞ suffices. © 1995 John Wiley & Sons, Inc.
Tail bounds for occupancy and the satisfiability threshold conjecture
Authors: Kamath Anil , Motwani Rajeev , Palem Krishna , Spirakis Paul 
Published: May 2007

AbstractThe classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well‐known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3‐SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈︁ 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3‐SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.
The variance of a partial match retrieval in a multidimensional symmetric trie
Authors: Schachinger Werner 
Published: May 2007

AbstractLet N records be stored in an M‐dimensional trie (M‐d trie). It is shown that under the symmetric Bernoulli model the variance of the cost CNω of a partial match retrieval is magnified image with continuous periodic function τω, where u is the number of unspecified components in a query ω of size M. This confirms in quantitative manner a conjecture by Kirschenhofer, Prodinger, and Szpankowski [Int. J. Found. Comput. Sci., 4, 69–84 (1993)], who presented a detailed analysis of Var CNω in the M = 2, u = 1‐case, but used in their proof a transformation formula of Ramanujan, which does not seem to have an analogue for M > 2. Our analysis is based on exponential approximations and Mellin inversion.
Bounded branching process and and/or tree evaluation
Authors: Karp Richard M. , Zhang Yanjun 
Published: May 2007

AbstractWe study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process {Zn} with a bounded offspring distribution, we derive a tight bound, decaying super‐exponentially fast as c increases, on the probability Pr[Zn > cE(Zn)], and a similar bound on the probability Pr[Zn ≤ E(Zn)/c] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two‐type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.
Hypergeometrics and the cost structure of quadtrees
Authors: Flajolet Philippe , Labelle Gilbert , Laforest Louise , Salvy Bruno 
Published: May 2007

AbstractSeveral characteristic parameters of randomly grown quadtrees of any dimension are analyzed. Additive parameters have expectations whose generating functions are expressible in terms of generalized hypergeometric functions. A complex asymptotic process based on singularity analysis and integral representations akin to Mellin transforms leads to explicit values for various structure constants related to path length, retrieval costs, and storage occupation.
A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Authors: Jerrum Mark 
Published: May 2007

AbstractA fully polynomial randomized approximation scheme is presented for estimating the number of (vertex) k‐colorings of a graph of maximum degree Δ, when k ≥ 2Δ + 1. © 1995 John Wiley & Sons, Inc.