A central challenge in network design is ensuring resilience: how can we guarantee multiple, independent, communication pathways between nodes, even when some connections fail in a network? In 1989, Zehavi and Itai formulated a graph-theoretic conjecture that captures the essence of this problem. They proposed that any \(k\)-vertex-connected graph contains \(k\) independent spanning trees rooted at any given root \(r\), which means that for every vertex \(v\) in the graph, the unique \(r-v\) paths within these \(k\) spanning trees are entirely disjoint, apart from their endpoints \(r\) and \(v\). Despite decades of effort, this conjecture has only been proven for \(k \le 4\) and for specific graph families using their underlying topological structure, leaving the general case as an open problem in graph theory with substantial consequences in the field of distributed algorithms.

A 0/1-polytope in \(\mathbb R^n\) is the convex hull of a subset of \(\{0,\, 1\}^n\). The graph of a polytope \(P\) is the graph whose vertices are the zero-dimensional faces of \(P\) and whose edges are the one-dimensional faces of \(P\). A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every 0/1-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of \(\{0,\, 1\}^n\) independently at random with probability \(p \in (0; 1)\). Improving earlier results, we show that, for any \(p \in (0; 1)\), with high probability the edge expansion of the random 0/1-polytope is bounded from below by an absolute constant.

We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph G(n,p) with constant diameter with high probability. We get a tight (up to a constant factor) answer for all p > n^{-1+o(1)} outside "threshold windows" around n^{-k/(k+1)+o(1)}, k ∈ ℤ_{> 0}: with high probability the query complexity equals Θ(n^{4-d}p^{2-d}), where d is the diameter of the random graph. This demonstrates the following non-monotone behaviour: the query complexity jumps down at moments when the diameter gets larger; yet, between these moments the query complexity grows. We also show that there exists a non-adaptive algorithm that reconstructs the random graph with O(n^{4-d}p^{2-d}ln n) distance queries with high probability, and this is best possible.

Abstract. It is known that the complete graph [Formula: see text] contains a pancyclic subgraph with [Formula: see text] edges, and that there is no pancyclic graph on [Formula: see text] vertices with fewer than [Formula: see text] edges. We show that, with high probability, [Formula: see text] contains a pancyclic subgraph with [Formula: see text] edges for [Formula: see text], where [Formula: see text], which is right above the threshold for pancyclicity.

Consider the random subgraph process on a base graph $G$ on $n$ vertices: a sequence $\lbrace G_t \rbrace _{t=0} ^{|E(G)|}$ of random subgraphs of $G$ obtained by choosing an ordering of the edges of $G$ uniformly at random, and by sequentially adding edges to $G_0$, the empty graph on the vertex set of $G$, according to the chosen ordering. We show that if $G$ has one of the following properties: 1. there is a positive constant $\varepsilon > 0$ such that $\delta (G) \geq \left( \frac{1}{2} + \varepsilon \right) n$; 2. there are some constants $\alpha, \beta >0$ such that every two disjoint subsets $U,W$ of size at least $\alpha n$ have at least $\beta |U||W|$ edges between them, and the minimum degree of $G$ is at least $(2\alpha + \beta )\cdot n$; or 3. $G$ is an $(n,d,\lambda )$-graph, with $d\geq \frac{C\cdot n\cdot \log \log n}{\log n}$ and $\lambda \leq \frac{c\cdot d^2}{n}$ for some absolute constants $c,C>0;$ then for a positive integer constant $k$ with high probability the hitting time of the property of containing $k$ edge disjoint Hamilton cycles is equal to the hitting time of having minimum degree at least $2k$. These results extend prior results by Johansson and by Frieze and Krivelevich and answer a question posed by Frieze.

We present an explicit connected spanning structure that appears in a random graph just above the connectivity threshold with high probability.

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: For a graph H, we denote by Hq the graph obtained from H by subdividing its edges with q–1 vertices each. We show that the k-size-Ramsey number Ŗk(Hq) satisfies Ŗk(Hq) = O(qn) for every bounded degree graph H on n vertices and for q = Ω(log n), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an (n, d, λ)-graph with λ = O(d1 – ∊), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/4 vertices from . Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in , and each path is of the same length . Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).

We first consider the following problem. We are given a fixed perfect matching $M$ of $[n]$ and we add random edges one at a time until there is a Hamilton cycle containing $M$. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions.

We show that every locally sparse graph contains a linearly sized expanding subgraph. For constants c_1>c_2>1, 0<\alpha<1, a graph G on n vertices is called a (\c_1,c_2,\alpha)-graph if it has at least c_1n edges, but every vertex subset W\subset V(G) of size |W|łe \alpha n spans less than c_2|W| edges. We prove that every (c_1,c_2,\alpha)-graph with bounded degrees contains an induced expander on linearly many vertices. The proof can be made algorithmic. We then discuss several applications of our main result to random graphs, to problems about embedding graph minors, and to positional games.

We show that for any fixed dense graph $G$ and bounded-degree tree $T$ on the same number of vertices, a modest random perturbation of $G$ will typically contain a copy of $T$. This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c=c(\alpha,\Delta)$ such that if $G$ is an $n$-vertex graph with minimum degree at least $\alpha n$, and $T$ is an $n$-vertex tree with maximum degree at most $\Delta$, then if we add $cn$ uniformly random edges to $G$, the resulting graph will contain $T$ asymptotically almost surely (as $n\to\infty$). Our proof uses a lemma concerning the decomposition of a dense graph into superregular pairs of comparable sizes, which may be of independent interest.

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors, where r > 1 is the activation threshold. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m(G, r) be the minimal size of a contagious set. It is known that for every d-regular or nearly d-regular graph on n vertices, . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion properties imply that (and more generally, . In addition, we demonstrate that rather weak assumptions on the girth and/or the spectral gap suffice in order to imply that . For example, we show this for graphs of girth at least 7, and for graphs with λ(G) < (1 − ε)d, provided the graph has no 4-cycles. Our results are algorithmic, entailing simple and effcient algorithms for selecting contagious sets.

We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games where Maker is constrained to choose edges of a walk or path in a given graph $G$, with the goal of visiting as many vertices of the underlying graph as possible.

We study two extremal problems about subgraphs excluding a family $\mathcal{F}$ of graphs: (i) Among all graphs with $m$ edges, what is the smallest size $f(m,\mathcal{F})$ of a largest $\mathcal{F}$-free subgraph? (ii) Among all graphs with minimum degree $\delta$ and maximum degree $\Delta$, what is the smallest minimum degree $h(\delta,\Delta,\mathcal{F})$ of a spanning $\mathcal{F}$-free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $\mathcal{F}$ is composed of all even cycles of length at most 2r, $r\geq 2$. In this case, we give bounds on $f(m,\mathcal{F})$ and $h(\delta,\Delta,\mathcal{F})$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$, we show the existence of subgraphs with arbitrarily high girth and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.

The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edge set of $G$ at random (usually adding few random edges to $G$) typically results in a graph having much “nicer” properties. In this work, we study smoothed analysis on trees or, equivalently, on connected graphs. Given an $n$-vertex connected graph $G$, form a random supergraph $G^*$ of $G$ by turning every pair of vertices of $G$ into an edge with probability $\frac{\varepsilon}{n}$, where $\varepsilon$ is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have a very large diameter, and can possibly contain no long paths. In contrast, we show that if $G$ is an $n$-vertex connected graph, then typically $G^*$ has edge expansion $\Omega(\frac{1}{\log n})$, diameter $O(\log n)$, and vertex expansion $\Omega(\frac{1}{\log n})$ and contains a path of length $\Omega(n)$, where for the last two properties we additionally assume that $G$ has bounded maximum degree. Moreover, we show that if $G$ has bounded degeneracy, then typically the mixing time of the lazy random walk on $G^*$ is $O(\log^2 n)$. All these results are asymptotically tight.

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an n-vertex connected graph G, form a random supergraph of G* of G by turning every pair of vertices of G into an edge with probability epsilon/n, where epsilon is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if G is an n-vertex connected graph then typically G* has edge expansion Omega(1/(log n)), diameter O(log n), vertex expansion Omega(1/(log n)), and contains a path of length Omega(n), where for the last two properties we additionally assume that G has bounded maximum degree. Moreover, we show that if G has bounded degeneracy, then typically the mixing time of the lazy random walk on G* is O(log^2(n)). All these results are asymptotically tight.

We prove that the number of Hamilton cycles in the random graph $G(n,p)$ is $n!p^n(1+o(1))^n$ asymptotically almost surely (a.a.s.), provided that $p\geq \frac{\ln n+\ln\ln n+\omega(1)}{n}$. Furthermore, we prove the hitting time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree $2$ creates $(\frac{\ln n}{e})^n(1+o(1))^n$ Hamilton cycles a.a.s.

Given a class of graphs F, we say that a graph G is universal for F, or F-universal, if every H ∊ F is contained in G as a subgraph. The construction of sparse universal graphs for various families F has received a considerable amount of attention. One is particularly interested in tight F-universal graphs, i.e., graphs whose number of vertices is equal to the largest number of vertices in a graph from F. Arguably, the most studied case is that when F is some class of trees. Given integers n and Δ, we denote by T(n, Δ) the class of all n-vertex trees with maximum degree at most Δ. In this work, we show that every n-vertex graph satisfying certain natural expansion properties is T(n, Δ)-universal or, in other words, contains every spanning tree of maximum degree at most Δ. Our methods also apply to the case when Δ is some function of n. The result has a few very interesting implications. Most importantly, since random graphs are known to be good expanders, we obtain that the random graph G(n, p) is asymptotically almost surely (a.a.s.) universal for the class of all bounded degree spanning (that is, n-vertex) trees provided that p ≥ cn−1/3 log n where c > 0 is a constant. Moreover, a corresponding result holds for the random regular graph of degree pn. In fact, we show that if Δ satisfies log n ≤ Δ ≤ n1/3, then the random graph G(n, p) with p ≥ cΔn−1/3 log n and the random r-regular n-vertex graph with r ≥ cΔn2/3 log n are a.a.s. universal for T(n, Δ). Another interesting consequence is the existence of locally sparse n-vertex graphs that are universal for T(n, Δ). For Δ ∊ O(1), we show that one can (randomly) construct n-vertex T(n, Δ)-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton, and Rosenberg (1989), whose T(n, Δ)-universal graphs with merely O(n) edges contain large cliques of size Ω(Δ). We also derive some lower bounds and show that there exist very good expanders which are not universal for T(n, Δ). In particular, we see that there are expanders of minimum degree Ω(n/log n) which are not T(n, c√n)-universal. Finally, we show robustness of random graphs with respect to being universal for T(n, Δ) in the context of the Maker-Breaker tree-universality game.

We study the problem of creating a copy of some fixed graph H in the Achlioptas process on n vertices with parameter r, where $r=r(n)$ is a growing function of n. We prove general upper and lower bounds on the threshold of this problem, and derive exact threshold functions for the case where H is a tree, a cycle, or the complete graph on four vertices.

We prove that there exists a positive constant $\varepsilon$ such that if $\log n / n \leq p \leq n^{-1+\varepsilon}$, then asymptotically almost surely the random graph $G \sim G(n,p)$ contains a collection of $\lfloor \delta(G)/2 \rfloor$ edge-disjoint Hamilton cycles.

We analyze classical Maker-Breaker games played on the edge set of a randomly generated graph G.We consider the random graph process and analyze, for each of the properties "being spanning k-vertex-connected" , "admitting a perfect matching", and "being Hamiltonian", the first time when Maker starts having a winning strategy for building a graph possessing the target property (the so called hitting time).We prove that typically it happens precisely at the time the random graph process first reaches minimum degree 2k, 2 and 4, respectively, which is clearly optimal.The latter two statements settle conjectures of Stojaković and Szabó.We also consider a general-purpose game, the expander game, which is a main ingredient of our proofs and might be of an independent interest.

Consider a 3-uniform hypergraph H with n vertices. A tight Hamilton cycle C ⊂ H is a collection of n edges for which there is an ordering of the vertices v1, …, vn where every triple of consecutive vertices {vi, vi+1, vi+2} is an edge of C (indices considered modulo n). We develop new techniques which show that under certain natural pseudo-random conditions, almost all edges of H can be covered by edge-disjoint tight Hamilton cycles, for n divisible by 4. Consequently, random 3-uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo-random digraphs with even numbers of vertices.

Let [Formula: see text] be a sequence of [Formula: see text] integers. For an increasing monotone graph property [Formula: see text] we say that a base graph [Formula: see text] is [Formula: see text]-resilient with respect to [Formula: see text] if for every subgraph [Formula: see text] such that [Formula: see text] for every [Formula: see text] the graph [Formula: see text] possesses [Formula: see text]. This notion naturally extends the idea of the local resilience of graphs recently initiated by Sudakov and Vu. In this paper we study the [Formula: see text]-resilience of a typical graph from [Formula: see text] with respect to the Hamiltonicity property, where we let [Formula: see text] range over all values for which the base graph is expected to be Hamiltonian. Considering this generalized approach to the notion of resilience our main result implies several corollaries which improve on the best known bounds of Hamiltonicity related questions. For one, it implies that for every positive [Formula: see text] and large enough values of [Formula: see text], if [Formula: see text], then with high probability the local resilience of [Formula: see text] with respect to being Hamiltonian is at least [Formula: see text], improving on the previous bound for this range of [Formula: see text]. Another implication is a result on optimal packing of edge-disjoint Hamilton cycles in a random graph. We prove that if [Formula: see text], then with high probability a graph [Formula: see text] sampled from [Formula: see text] contains [Formula: see text] edge-disjoint Hamilton cycles, extending the previous range of [Formula: see text] for which this was known to hold.

Let $\mathbf{d}=d_1\leq d_2\leq\dots\leq d_n$ be a nondecreasing sequence of n positive integers whose sum is even. Let $\mathcal{G}_{n,\mathbf{d}}$ denote the set of graphs with vertex set $[n]=\{1,2,\dots,n\}$ in which the degree of vertex i is $d_i$. Let $G_{n,\mathbf{d}}$ be chosen uniformly at random from $\mathcal{G}_{n,\mathbf{d}}$. It will be apparent from section 4.3 that all of the sequences we are considering will be graphic. We give a condition on $\mathbf{d}$ under which we can show that whp $\mathcal{G}_{n,\mathbf{d}}$ is Hamiltonian. This condition is satisfied by graphs with exponential tails as well those with power law tails.

We prove that if T is a tree on n vertices with maximum degree $\Delta$ and the edge probability $p(n)$ satisfies $np\geq C\max\{\Delta\log n,n^{\epsilon}\}$ for some constant $\epsilon>0$, then with high probability the random graph $G(n,p)$ contains a copy of T. The obtained bound on the edge probability is shown to be essentially tight for $\Delta=n^{\Theta(1)}$.

A graph G on n vertices is pancyclic if it contains cycles of length t for all $3\leq t\leq n$. In this paper we prove that for any fixed $\epsilon>0$, the random graph $G(n,p)$ with $p(n)\gg n^{-1/2}$ (i.e., with $p(n)/n^{-1/2}$ tending to infinity) asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most $(1/2-\epsilon)np$, then $G-H$ is pancyclic. In fact, we prove a more general result which says that if $p\gg n^{-1+1/(l-1)}$ for some integer $l\geq3$, then for any $\epsilon>0$, asymptotically almost surely every subgraph of $G(n,p)$ with minimum degree greater than $(1/2+\epsilon)np$ contains cycles of length t for all $l\leq t\leq n$. These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant $1/2$ in the assumption for the minimum degree. We also prove corresponding results for pseudorandom graphs.

In this paper we study the model of ∊-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d ≥ ∊−-kln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊−-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2k/k2) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e., a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph $\mathrm{UG}(D)$ is $O(k\log k)$, and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(k\log^2k)}\cdot n^{O(1)}$ whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is $2^{O(k\log k)}\cdot n^{O(1)}$.

In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \Theta(n)$, where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., “What is the ith neighbor of vertex v?”), vertex-pair queries (i.e., “Is there an edge between vertices v and u?”), and degree queries (i.e., “What is the degree of vertex v?”). Our main finding is a lower bound of $\Omega(n^{1/3})$ on the necessary number of queries that holds for every $d < n^{1-\nu(n)}$, where $\nu(n) = o(1)$. Since when $d = \Theta(n)$ the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. This lower bound holds for testing H-freeness of every nonbipartite subgraph H. Additionally, we provide sublinear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds. Finally, in the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the “correct” edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.

For a real $c \geq 1$ and an integer n, let $f(n,c)$ denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least $f(n,1)$ vertices. The problem of estimating $f(n,1)$ was posed long ago by Erdős, Fajtlowicz, and Staton. In this paper we obtain the following upper and lower bounds for the asymptotic behavior of $f(n,c)$: (i) For fixed $c>2.1$, $n^{1-O(1/c)} \leq f(n,c) \leq O(cn/\log n)$. (ii) For fixed $c=1+\varepsilon$ with $\varepsilon>0$ sufficiently small, $f(n,c) \geq n^{\Omega(\varepsilon^2/ \ln (1/\varepsilon))}$. (iii) $\Omega (\ln n) \leq f(n,1) \leq O(n^{1/2} \ln^{3/4} n)$. An analogous problem for not necessarily induced subgraphs is briefly considered as well.

Let m and b be positive integers, and let F be a hypergraph. In an $(m,b)$ Maker-Breaker game F two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of F. Maker selects m vertices per move, and Breaker selects b vertices per move. The game ends when every vertex has been claimed by one of the players. Maker wins if he claims all of the vertices of some hyperedge of F; otherwise Breaker wins. An $(m,b)$ Avoider-Enforcer game F is played in a similar way. The only difference is in the determination of the winner: Avoider loses if he claims all of the vertices of some hyperedge of F; otherwise Enforcer loses. In this paper we consider the Maker-Breaker and Avoider-Enforcer versions of the planarity game, the k-colorability game, and the $K_t$-minor game.

The cycle packing number ν e ( G ) of a graph G is the maximum number of pairwise edge-disjoint cycles in G . Computing ν e ( G ) is an NP-hard problem. We present approximation algorithms for computing ν e ( G ) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio Θ(√log n ), where n = | V ( G )|. This improves upon the previous O (log n ) upper bound for the approximation ratio of this algorithm. In the directed case we present a √ n -approximation algorithm. Finally, we give an O ( n 2/3 )-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of ν e ( G ) in directed graphs. Specifically, we prove a lower bound of Ω(log n /loglog n ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate ν e ( G ) within a factor of O (log 1 − ε n ) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.

It is known that random k-SAT instances with at least $cn$ clauses, where $c =\nobreak c_k$ is a suitable constant, are unsatisfiable (with high probability). We consider the problem to certify efficiently the unsatisfiability of such formulas. A backtracking-based algorithm of Beame et al. [SIAM J. Comput.,} 31 (2002), pp. 1048--1075] shows that k-SAT instances with at least $n^{k-1}/(\log n)^{k-2}$ clauses can be certified unsatisfiable in polynomial time. We employ spectral methods to improve on this bound. For even $k\ge 4$ we present a polynomial time algorithm which certifies random k-SAT instances with at least $n^{(k/2)+o(1)}$ clauses as unsatisfiable (with high probability). For odd k we focus on 3-SAT instances and obtain an efficient algorithm for formulas with at least $n^{3/2+\varepsilon}$ clauses, where $\varepsilon >0$ is an arbitrary constant.

The strong chromatic index of a graph G, denoted by $\chi_s(G)$, is the minimum number of colors needed to color its edges so that each color class is an induced matching. In this paper we analyze the asymptotic behavior of this parameter in a random graph $G(n,p)$, for two regions of the edge probability $p=p(n)$. For the dense case, where p is a constant, $0 < p < 1$, we prove that with high probability $\chi_s(G)\le (1+o(1))\frac{3}{4}\frac{n^2p}{\log_bn}$, where $b=1/(1-p)$. This improves upon a result of Czygrinow and Nagle [{\it Discrete Math.}, 281 (2004), pp. 129--136]. For the sparse case, where $np< \frac{1}{100}\sqrt{\log n/\log\log n}$, we show that with high probability $\chi_s(G)=\Delta_1(G)$, where $\Delta_1(G)=\max\{d(u)+d(v)-1:\ (u,v)\in E(G)\}$. This improves a result of Palka [{\it Australas. J. Combin.}, 18 (1998), pp. 219--226].

A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits. We show that the Reed-Muller codes of constant order are locally testable. Specifically, we describe an efficient randomized algorithm to test if a given vector of length n=2/sup m/ is a word in the rth-order Reed-Muller code R(r,m) of length n=2/sup m/. For a given integer r/spl ges/1, and real /spl epsi/>0, the algorithm queries the input vector /spl upsi/ at O(1//spl epsi/+r2/sup 2r/) positions. On the one hand, if /spl upsi/ is at distance at least /spl epsi/n from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if /spl upsi/ is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r,m) must perform /spl Omega/(1//spl epsi/+2/sup r/) queries.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is $\tilde{\Theta}(\sqrt{n})$, where n is the number of vertices in the graph (and $\tilde{\Theta}(f(n))$ means $\Theta(f(n)\cdot{\rm polylog}(f(n)))$). Thus there is a large gap between the complexity of testing in the two cases. In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is $\tilde{O}(\min(\sqrt{n},n^2/m))$, where m is the number of edges in the graph, and we match it with an almost tight lower bound.

We prove a general recursive inequality concerning /spl mu//sup */(R), the asymptotic (least) density of the best binary covering codes of radius R. In particular, this inequality implies that /spl mu//sup */(R)/spl les/e/spl middot/(RlogR+logR+loglogR+2), which significantly improves the best known density 2/sup R/R/sup R/(R+1)/R!. Our inequality also holds for covering codes over arbitrary alphabets.

Let G be a graph on n vertices and suppose that at least $\epsilon n^2$ edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on $c k\,{\rm ln}\,k/ \epsilon^2$ vertices are not k-colorable, where c > 0 is an absolute constant. If G is as above for k=2, then most induced subgraphs on $\frac{({\rm ln} (1/\epsilon))^b}{\epsilon}$ are nonbipartite, for some absolute positive constant b, and this is tight up to the polylogarithmic factor. Both results are motivated by the study of testing algorithms for k-colorability, first considered by Goldreich, Goldwasser, and Ron in, [J. ACM, 45 (1998), pp. 653--750], and improve the results in that paper.

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language $L\in \{0,1\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\in L$ and rejects it with high probability if w has to be modified in at least $\epsilon n$ positions to create a word in L. The algorithm queries $\tilde{O}(1/\epsilon)$ bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in $1/\epsilon$. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of $\epsilon$. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.