Edge‐disjoint Hamiltonian cycles in hypertournaments

We introduce a method for reducing k‐tournament problems, for k ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a k‐tournament on n ≥ k + 1 + 24d vertices (when k ≥ 4) or on n ≥ 30d + 2 vertices (when k = 3) has d edge‐disjoint Hamiltonian cycles if and only if it is d‐edge‐connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k ≥ 3. We also characterizatize the pancyclic k‐tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k.). © 2005 Wiley Periodicals, Inc. J Graph Theory     

On smoothed analysis in dense graphs and formulas

We study a model of random graphs, where a random instance is obtained by adding random edges to a large graph of a given density. The research on this model has been started by Bohman and colleagues (Random Struct Algor 3 ; Random Struct Algor 4 ). Here we obtain a sharp threshold for the appearance of a fixed subgraph and for certain Ramsey properties. We also consider a related model of random k‐SAT formulas, where an instance is obtained by adding random k‐clauses to a fixed formula with a given number of clauses, and derive tight bounds for the non‐satisfiability of the thus‐obtained random formula. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Coloring uniform hypergraphs with few colors

Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2ⁿ, then m(r, k) ≥ ?(k)k^r(r/ln r)^n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

A remark on divisibility of definable groups

We show that if G is a definably compact, definably connected definable group defined in an arbitrary o‐minimal structure, then G is divisible. Furthermore, if G is defined in an o‐minimal expansion of a field, k ∈ ? and p_k : G → G is the definable map given by p_k (x ) = x^k for all x ∈ G , then we have |(p_k )^–1(x )| ≥ k^r for all x ∈ G , where r > 0 is the maximal dimension of abelian definable subgroups of G . (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Coloring complete bipartite graphs from random lists

Let K_n,n be the complete bipartite graph with n vertices in each side. For each vertex draw uniformly at random a list of size k from a base set S of size s = s(n). In this paper we estimate the asymptotic probability of the existence of a proper coloring from the random lists for all fixed values of k and growing n. We show that this property exhibits a sharp threshold for k ≥ 2 and the location of the threshold is precisely s(n) = 2n for k = 2 and approximately for k ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On the threshold for k-regular subgraphs of random graphs

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On weights of induced paths and cycles in claw‐free and K1,r‐free graphs

Let G be a K_1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K_1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001     

Random k‐SAT and the power of two choices

We study an Achlioptas‐process version of the random k‐SAT process: a bounded number of k‐clauses are drawn uniformly at random at each step, and exactly one added to the growing formula according to a particular rule. We prove the existence of a rule that shifts the satisfiability threshold. This extends a well‐studied area of probabilistic combinatorics (Achlioptas processes) to random CSP's. In particular, while a rule to delay the 2‐SAT threshold was known previously, this is the first proof of a rule to shift the threshold of k‐SAT for . We then propose a gap decision problem based upon this semi‐random model. The aim of the problem is to investigate the hardness of the random k‐SAT decision problem, as opposed to the problem of finding an assignment or certificate of unsatisfiability. Finally, we discuss connections to the study of Achlioptas random graph processes. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 163–173, 2015     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Tight Hamilton cycles in random uniform hypergraphs

In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Minimality conditions on circularly ordered structures

We explore analogues of o‐minimality and weak o‐minimality for circularly ordered sets. Much of the theory goes through almost unchanged, since over a parameter the circular order yields a definable linear order. Working over ?? there are differences. Our main result is a structure theory (with infinitely many doubly transitive examples related to Jordan permutation groups) for ?₀‐categorical weakly circularly minimal structures. There is a 5‐homogeneous (or ‘5‐indiscernible’) example which is not 6‐homogeneous, but any example which is k‐homogeneous for some k ≥ 6 is k‐homogeneous for all k. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

The property of having a k ‐regular subgraph has a sharp threshold

In this paper it is proved that in the random graph model G(n,p), the property of containing a k ‐regular subgraph, has a sharp threshold for k ≥ 3. It is also shown how to use similar methods to prove, quite easily, the (known fact of) sharpness of having a non empty k ‐core for k ≥ 3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 509–519, 2013     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

The generalized acyclic edge chromatic number of random regular graphs

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006     

Limit distribution of the number of consecutive records

A succinct series expression is derived for describing the limit distribution of the number of times r consecutive elements are all records (in a sequence of independent and identically distributed random variables with a common continuous distribution) for all r ≥ 2. Previously, only the limit distributions for r = 1, 2, and 3 were known. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Powers of tight Hamilton cycles in randomly perturbed hypergraphs

For k ≥ 2 and r ≥ 1 such that k + r ≥ 4, we prove that, for any α > 0, there exists ε > 0 such that the union of an n‐vertex k‐graph with minimum codegree and a binomial random k‐graph with on the same vertex set contains the rth power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft.     

Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random k ‐coloring of an n ‐vertex graph with maximum degree Δ. We prove that, for every ε > 0, the dynamics converges to a random coloring within O(nlog n) steps assuming k ≥ k₀(ε) and either: (i) k/Δ > α* + ε where α*≈? 1.763 and the girth g ≥ 5, or (ii) k/Δ >β * + ε where β*≈? 1.489 and the girth g ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on k/Δ and the minimum girth but also required Δ = Ω (log n). The best known result for general graphs is O(nlog n) mixing time when k/Δ > 2 and O(n²) mixing time when k/Δ > 11/6. Related results of Goldberg et al apply when k/Δ > α* for all Δ ≥ 3 on triangle‐free “neighborhood‐amenable” graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Randomized greedy algorithms for finding small k‐dominating sets of regular graphs

A k‐dominating set of a graph G is a subset ?? of the vertices of G such that every vertex of G is either in ?? or at distance at most k from a vertex in ??. It is of interest to find k‐dominating sets of small cardinality. In this paper we consider simple randomized greedy algorithms for finding small k‐dominating sets of regular graphs. We analyze the average‐case performance of the most efficient of these simple heuristics showing that it performs surprisingly well on average. The analysis is performed on random regular graphs using differential equations. This, in turn, proves upper bounds on the size of a minimum k‐dominating set of random regular graphs. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 22, 2005