Maximum independent sets on random regular graphs

We determine the asymptotics of the independence number of the random d-regular graph for all \({d\geq d_0}\). It is highly concentrated, with constant-order fluctuations around \({n\alpha_*-c_*\log n}\) for explicit constants \({\alpha_*(d)}\) and \({c_*(d)}\). Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.     

Maximum matchings in sparse random graphs: Karp–Sipser revisited

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G_{n, c/n}, where c>0 is constant. The algorithm was first proposed by Karp and Sipser [Proceedings of the Twenty-Second Annual IEEE Symposium on Foundations of Computing, 1981, pp. 364–375]. We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where c<e we show that the algorithm finds a maximum matching with high probability. If c>e then with high probability the algorithm produces a matching which is within n^1/5+o(1) of maximum size. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 111–177, 1998     

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in $O\left(n^3\right)$-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in $O\left(n^4\right)$-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

On the probability of independent sets in random graphs

Let k be the asymptotic value of the independence number of the random graph G(n, p). We prove that if the edge probability p(n) satisfies p(n) ? n^?2/5ln^6/5n then the probability that G(n, p) does not contain an independent set of size k ? c, for some absolute constant c > 0, is at most exp{?cn²/(k⁴p)}. We also show that the obtained exponent is tight up to logarithmic factors, and apply our result to obtain new bounds on the choice number of random graphs. We also discuss a general setting where our approach can be applied to provide an exponential bound on the probability of certain events in product probability spaces. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 1–14, 2003     

Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables

We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L| = n and |R| = m. We construct a random graph G by allowing each x∈L to choose d random neighbours in R. The question discussed is as to the size μ(G) of the largest matching in G. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(G) = n whp? We answer this question exactly when d is at least three. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Maximum independent sets in 3- and 4-regular Hamiltonian graphs

Smooth 4-regular Hamiltonian graphs are generalizations of cycle-plus-triangles graphs. While the latter have been shown to be 3-choosable, 3-colorability of the former is NP-complete. In this paper we first show that the independent set problem for 3-regular Hamiltonian planar graphs is NP-complete, and using this result we show that this problem is also NP-complete for smooth 4-regular Hamiltonian graphs. We also show that this problem remains NP-complete if we restrict the problem to the existence of large independent sets (i.e., independent sets whose size is at least one third of the order of the graphs).     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016     

Maximum acyclic and fragmented sets in regular graphs

We show that a typical d‐regular graph G of order n does not contain an induced forest with around vertices, when n ? d ? 1, this bound being best possible because of a result of Frieze and ?uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008     

On distance -dominating and -independent sets in sparse graphs

Dvořák [European J. Combin. 34 (2013), pp. 833–840] gave a bound on the minimum size of a distance -dominating set in terms of the maximum size of a distance -independent set and generalized coloring numbers, thus obtaining a constant-factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using a linear programming (LP)-based argument inspired by the work of Bansal and Umboh [Inform. Process. Lett. 122 (2017), pp. 21–24].     

Local convergence results of Gauss-Newton's like method in weak conditions

In this paper, we study the convergence of Gauss-Newton's like method for nonlinear least squares problems. Under the hypothesis that derivative satisfies some kind of weak Lipschitz condition, we obtain the sharp estimates of the radii of convergence ball of Gauss-Newton's like method and the uniqueness ball of the solution.     

Projectivity and independent sets in powers of graphs

We investigate the relationship between projectivity and the structure of maximal independent sets in powers of circular graphs, Kneser graphs and truncated simplices. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 162–171, 2002     

On feedback vertex sets and nonseparating independent sets in cubic graphs

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G ? F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G ? J is connected. f(G), z(G) denote the cardinalities of a minimum fvs and a maximum nsis, respectively, of G. The equation f(G) = n/2 ? z(G) + 1 and two new upper bounds on f(G) are derived for cubic graphs G.