On triangle‐free random graphs

We show that for every k≥1 and δ>0 there exists a constant c>0 such that, with probability tending to 1 as n→∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M≥cn^3/2 edges can be made bipartite by deleting ⌊δM⌋ edges. As an immediate consequence of this fact we infer that if M/n^3/2→∞ but M/n²→0, then the probability that a random graph G(n, M) contains no triangles decreases as 2^−(1+o(1))M. We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000     

On factors in random graphs

The following result is proved: LetG _n,p be a random graph withn vertices and probabilityp for an edge. Ifp is such that the random graph has min-degree at leastr with probability 1, then anyf-factor 1≦f≦r exists with probability 1, asn→∞.     

K‐linked graphs with girth condition

Recently, Mader [ 7 ] proved that every 2k‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004     

Applying geometric K‐cycles to fractional indices

A geometric model for twisted K‐homology is introduced. It is modeled after the Mathai–Melrose–Singer fractional analytic index theorem in the same way as the Baum–Douglas model of K‐homology was modeled after the Atiyah–Singer index theorem. A natural transformation from twisted geometric K‐homology to the new geometric model is constructed. The analytic assembly mapping to analytic twisted K‐homology in this model is an isomorphism for torsion twists on a finite ‐complex. For a general twist on a smooth manifold the analytic assembly mapping is a surjection. Beyond the aforementioned fractional invariants, we study T‐duality for geometric cycles.     

On the max‐cut of sparse random graphs

We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max‐Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value . It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of .     

On random k‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph with large minimum degree. We fix a positive integer k and let G_k be the random subgraph where each independently chooses k random neighbors, making kn edges in all. When the minimum degree then G_k is k‐connected w.h.p. for ; Hamiltonian for k sufficiently large. When , then G_k has a cycle of length for . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function (or ) where . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017     

Rank‐width of random graphs

Rank‐width of a graph G, denoted by rw (G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514–528]. We investigate the asymptotic behavior of rank‐width of a random graph G(n, p). We show that, asymptotically almost surely, (i) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , then rw (G(n, p)) = ?1/3??o(n), (iii) if p = c/n and c>1, then rw (G(n, p))?rn for some r = r(c), and (iv) if p?c/n and c81, then rw (G(n, p))?2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in n whenever p = c/n for each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Maximum fractional factors in graphs

We prove that fractional k-factors can be transformed among themselves by using a new adjusting operation repeatedly. We introduce, analogous to Berge’s augmenting path method in matching theory, the technique of increasing walk and derive a characterization of maximum fractional k-factors in graphs. As applications of this characterization, several results about connected fractional 1-factors are obtained.     

On large‐girth regular graphs and random processes on trees

We study various classes of random processes defined on the regular tree T_d that are invariant under the automorphism group of T_d. The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

Almost‐spanning universality in random graphs

A graph G is said to be ‐universal if it contains every graph on at most n vertices with maximum degree at most Δ. It is known that for any and any natural number Δ there exists such that the random graph G(n, p) is asymptotically almost surely ‐universal for . Bypassing this natural boundary, we show that for the same conclusion holds when . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 380–393, 2017     

Dynamic choosability of triangle‐free graphs and sparse random graphs

Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have .     

Pseudo‐random properties of self‐complementary symmetric graphs

There are some results in the literature showing that Paley graphs behave in many ways like random graphs G(n, 1/2). In this paper, we extend these results to the other family of self‐complementary symmetric graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 310–316, 2004     

Threshold values of random K‐SAT from the cavity method

Using the cavity equations of Mézard, Parisi, and Zecchina 23 ; Mézard and Zecchina, 24 we derive the various threshold values for the number of clauses per variable of the random K‐satisfiability problem, generalizing the previous results to K ≥ 4. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large K. The stability of the solution is also computed. For any K, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold.© 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Vertex‐distinguishing edge colorings of random graphs

A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002     

Diameter in ultra‐small scale‐free random graphs

It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k^{?(τ ? 1)} with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree d_fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008