Tail bounds for occupancy and the satisfiability threshold conjecture

The 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.     

Vizing's coloring algorithm and the fan number

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010     

Turán-type results for partial orders and intersection graphs of convex sets

We prove Ramsey-type results for intersection graphs of geometric objects. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c > 0 such that for every family F of n convex sets in the plane, the intersection graph of F or its complement contains a balanced complete bipartite graph of size at least cn. There is a constant c > 0 such that for every family F of n x-monotone curves in the plane, the intersection graph G of F contains a balanced complete bipartite graph of size at least cn/log n or the complement of G contains a balanced complete bipartite graph of size at least cn. Our bounds rely on new Turán-type results on incomparability graphs of partially ordered sets.     

Minimax Problems Related to Cup Powers and Steenrod Squares

If F is a family of mod 2 k-cycles in the unit n-ball, we lower bound the maximal volume of any cycle in F in terms of the homology class of F in the space of all cycles. We give examples to show that these lower bounds are fairly sharp. Received: February 2007, Revision: January 2008, Accepted: January 2008     

Balanced coloring of bipartite graphs

Given a bipartite graph G(U∪V, E) with n vertices on each side, an independent set I∈G such that |U∩I|=|V∩I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χ_B(G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χ_B(G) in terms of the average degree $\bar{d}$ of G and in terms of the maximum degree Δ of G. In particular we prove the following:

• $\chi_{{{B}}}({{G}}) \leq {{max}} \{{{2}},\lfloor {{2}}\overline{{{d}}}\rfloor+{{1}}\}$.
• For any 0<ε<1 there is a constant Δ₀ such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥Δ₀ and n≥(1+ε)2Δ vertices on each side, then $\chi_{{{B}}}({{G}})\leq \frac{{{{20}}}}{\epsilon^{{{2}}}} \frac{\Delta}{{{{ln}}}\,\Delta}$.

© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

The characterization of zero-sum (mod 2) bipartite Ramsey numbers

Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Z_k) is the smallest integer t such that in every Z_k-coloring of the edges of K_t,t, there is a zero-sum mod k copy of G in K_t,t. In this article we give the first proof that determines B(G, Z₂) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z₂) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in K_n,n, and let F be a field. A function f : E(K_n,n) → F is called G-stable if every copy of G in K_n,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, K_n,n, F) is a linear space, which is called the K_n,n uniformity space of G over F. We determine U(G, K_n,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z₂, we can compute B(G, Z₂), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

Circular flow numbers of regular multigraphs

The circular flow number F_c(G) of a graph G = (V, E) is the minimum r ϵ ℚ such that G admits a flow ϕ with 1 ≤ ϕ (e) ≤ r − 1, for each e ϵ E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t+1)‐regular graphs (t ≥ 1). Our results imply that there are gaps for possible circular flow numbers for (2t+1)‐regular graphs, e.g., there is no cubic graph G with 3 < F_c(G) < 4. We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 24–34, 2001     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

Maximum k-colorable subgraphs

A lower bound is established on the number of edges in a maximum k-colorable subgraph of a loopless graph G. For the special case of 3-regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.     

Universality for bounded degree spanning trees in randomly perturbed graphs

We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G_α on n vertices with δ(G_α) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph G_α∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.     

The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

On characterizing Vizing's edge colouring bound

We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′(G)≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G. We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S?V(G) with |S|≥3, such that |E[S]|>((|S| ? 1)/2)(Δ + µ ? 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′(G)≤Δ + ?µ/?g/2??, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012     

On the greatest number of 2 and 3 colorings of a (v,e)-graph

Let F denote the family of simple undirected graphs on v vertices having e edges ((v, e)-graphs) and P(λ, G) be the chromatic polynomial of a graph G. For the given integers v, e, Δ, let f(v, e, Δ) denote the greatest number of proper colorings in Δ or less colors that a (v, e)-graph G can have, i.e., f(v, e, Δ) = max{P(Δ, G): G ∈ F}. In this paper we determine f(v, e, 2) and describe all graphs G for which P(2, G) = f(v, e, 2). For f(v, e, 3), a lower bound and an upper bound are found.     

Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins (q) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016     

On equality in an upper bound for domination parameters of graphs

We consider the well-known upper bounds μ(G) ≤|V(G)| − Δ(G), where Δ(G) denotes the maximum degree of G and μ(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of graphs for which equality does or does not hold and show that the difference between the domination and irredundance numbers can be arbitrary even when equality in the above bound holds for the domination number. © 1997 John Wiley & Sons, Inc.     

Coloring graphs which have equibipartite complements

If G is a graph of order $2n \geq 4$ with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is Δ (G)) if and only if G is not the union of two disjoint K_n's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement G is equibipartite with bipartition (A, D), and if both G and B, the induced bipartite subgraph of G with bipartition (A, D), have a 1-factor, then G is Type 1 (i.e., the total chromatic number of G is Δ (G) + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 183–194, 1997