Search

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first algorithm applies to $d$-regular, bipartite graphs satisfying a weak expansion condition: when $d$ is constant, and the graph is a bipartite $\Omega( \log^2 d/d)$-expander, we obtain an FPTAS for the number of independent sets. Previously such a result for $d>5$ was known only for graphs satisfying the much stronger expansion conditions of random bipartite graphs. The algorithm also applies to weighted independent sets: for a $d$-regular, bipartite $\alpha$-expander, with $\alpha>0$ fixed, we give an FPTAS for the hard-core model partition function at fugacity $\lambda=\Omega(\log d / d^{1/4})$. Finally we present an algorithm that applies to all $d$-regular, bipartite graphs, runs in time $\exp\left( O\left( n \cdot \frac{ \log^3 d }{d } \right) \right)$, and outputs a $(1 + o(1))$-approximation to the number of independent sets.

Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2n}$ or the complete bipartite graph $K_{n,n}$, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary $k$-regular bipartite graphs $G$ on $2n$ vertices for all $k = \omega \left( \frac{n}{\log^{1/3} n} \right)$. Surprisingly, this is not the case for smaller values of $k$. Using a construction due to Goel, Kapralov and Khanna, we show that there exist bipartite $k$-regular graphs in which the last isolated vertex disappears long before a perfect matching appears., Comment: Corrected typo

For a bipartite graph G, let h(G) be the largest t such that either G or the bipartite complement of G contain K$_{t,t}$. For a class F of graphs, let h(F)= min {h(G): G\in F}. We say that a bipartite graph H is strongly acyclic if neither H nor its bipartite complement contain a cycle. By Forb(n, H) we denote a set of bipartite graphs with parts of sizes n each, that do not contain H as an induced bipartite subgraph respecting the sides. One can easily show that h(Forb(n,H))= O(n$^{1-s}$) for a positive s if H is not strongly acyclic. Here, we prove that h(Forb(n, H)) is linear in n for all strongly acyclic graphs except for four graphs.

It is well-known that in every $r$-coloring of the edges of the complete bipartite graph $K_{m,n}$ there is a monochromatic connected component with at least ${m+n\over r}$ vertices. In this paper we study an extension of this problem by replacing complete bipartite graphs by bipartite graphs of large minimum degree. We conjecture that in every $r$-coloring of the edges of an $(X,Y)$-bipartite graph with $|X|=m$, $|Y|=n$, $\delta(X,Y) > \left( 1 - \frac{1}{r+1}\right) n$ and $\delta(Y,X) > \left( 1 - \frac{1}{r+1}\right) m$, there exists a monochromatic component on at least $\frac{m+n}{r}$ vertices (as in the complete bipartite graph). If true, the minimum degree condition is sharp (in that both inequalities cannot be made weak when $m$ and $n$ are divisible by $r+1$). We prove the conjecture for $r=2$ and we prove a weaker bound for all $r\geq 3$. As a corollary, we obtain a result about the existence of monochromatic components with at least $\frac{n}{r-1}$ vertices in $r$-colored graphs with large minimum degree.

International audience; A bipartite graph is a powerful abstraction for modeling relationships between two collections. Visualizations of bipartite graphs allow users to understand the mutual relationships between the elements in the two collections, e.g., by identifying clusters of similarly connected elements. However, commonly-used visual representations do not scale for the analysis of large bipartite graphs containing tens of millions of vertices, often resorting to an a-priori clustering of the sets. To address this issue, we present the Who’s-Active-On-What-Visualization (WAOW-Vis) that allows for multiscale exploration of a bipartite social-network without imposing an a-priori clustering. To this end, we propose to treat a bipartite graph as a high-dimensional space and we create the WAOW-Vis adapting the multiscale dimensionality-reduction technique HSNE. The application of HSNE for bipartite graph requires several modifications that form the contributions of this work. Given the nature of the problem, a set-based similarity is proposed. For efficient and scalable computations, we use compressed bitmaps to represent sets and we present a novel space partitioning tree to efficiently compute similarities; the Sets Intersection Tree. Finally, we validate WAOW-Vis on several datasets connecting Twitter-users and -streams in different domains: news, computer science and politics. We show how WAOW-Vis is particularly effective in identifying hierarchies of communities among social-media users.

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in -interval minor-free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of -interval minor-free graphs is studied.

Let G be a connected bipartite graph with colour classes E and V and root polytope Q. Regarding the hypergraph H=(V,E) induced by G, we prove that the interior polynomial of H is equivalent to the Ehrhart polynomial of Q, which in turn is equivalent to the h-vector of any triangulation of Q. It follows that the interior polynomials of H and its transpose H=(E,V) agree. When G is a complete bipartite graph, our result recovers a well-known hypergeometric identity due to Saalschütz. It also implies that certain extremal coefficients in the Homfly polynomial of a special alternating link can be read off of an associated Floer homology group., National Science Foundation (U.S.) (Grant DMS‐1100147), National Science Foundation (U.S.) (Grant DMS‐1362336)

Let G be a regular bipartite graph and X ⊆ E (G). We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph (G, X ) is not equivalent to (G, ∅). In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge.Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges.

Let G be a graph of order n satisfying that there exists for which every graph of order n and size t is contained in exactly λ distinct subgraphs of the complete graph isomorphic to G. Then G is called t-edge-balanced and λ the index of G. In this article, new examples of 2-edge-balanced graphs are constructed from bipartite graphs and some further methods are introduced to obtain more from old.

Let be a function on the vertex set of the graph . The graph G is f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, , is the minimum of , over all functions f such that G is f-choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d, then the usual choice number is at least , so they grow simultaneously. In this article, we show that can be bounded while the minimum degree . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph .

Bouchet's conjecture asserts that each signed graph which admits a nowhere-zero flow has a nowhere-zero 6-flow. We verify this conjecture for two basic classes of signed graphs-signed complete and signed complete bipartite graphs by proving that each such flow-admissible graph admits a nowhere-zero 4-flow and we characterise those which have a nowhere-zero 2-flow and a nowhere-zero 3-flow.

An edge-coloring of a graph G with colors 1,...,t is called an interval t-coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erdi¾?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erdi¾?s's counterexample is the smallest in a sense of maximum degree known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non-edge-colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.

A proper edge coloring of a graph with colors 1, 2, 3, ' is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is a,b-biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. We prove that all 3, 6-biregular graphs have interval colorings and that all 3, 9-biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for 3, 5-biregular, 4, 6-biregular, and 4, 8-biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings.

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a -design of order n. The existence problem of -designs has been completely solved for the graphs for , for , K2, 3 and K3, 3. In this paper, I prove that for all , if there exists a -design of order N, then there exists a -design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.

Let be a graph and the number of independent (vertex) sets of G. Then the Merrifield–Simmons conjecture states that the sign of the term only depends on the parity of the distance of the vertices in G. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.

Eigenvector centrality is a linear algebra based graph invariant used in various rating systems such as webpage ratings for search engines. A generalization of the eigenvector centrality invariant is defined which is motivated by the need to design rating systems for bipartite graph models of time-sensitive and other processes. The linear algebra connection and some applications are described., Comment: Published in Networks: Peteris Daugulis: A note on a generalization of eigenvector centrality for bipartite graphs and applications. Networks 59(2): 261-264 (2012)

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 © 2012 Wiley Periodicals, Inc.

Posa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n + k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts of equal size. Let F be a subgraph of G whose components are nontrivial paths. Let k be the number of edges in F, and let t1 and t2 be the numbers of components of F having odd and even length, respectively. We prove that G has a spanning cycle containing F if any two nonadjacent vertices in opposite partite sets have degree-sum at least n/2 + τ(F), where τ(F) = ⌈k/2⌉ + ɛ (here ɛ = 1 if t1 = 0 or if (t1, t2)∈{(1, 0), (2, 0)}, and ɛ = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n>3k. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:1–17, 2012 © 2012 Wiley Periodicals, Inc.

We present a new equivalence result between restricted b-factors in bipartite graphs and combinatorial t-designs. This result is useful in the construction of t-designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for the problem of finding t-designs that has a noteworthy advantage compared to the traditional set-covering formulation. We analyze some polyhedral properties of GPD, implement a branch-and-cut algorithm using it and solve several instances of small designs to compare with another point-block formulation found in the literature. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 169–182, 2006

A base of an action of a group G on a set $\Omega$ is a subset $B \subseteq \Omega$ such that the pointwise stabiliser of $B$ in $G$ is the identity. We prove that if $\Omega$ is the set of partitions of $[ 1, kl ]$ into $l$ subsets of size $k$ , then the action of $S_{kl}$ on $\Omega$ has a base of size two if and only if $k \geq 3$ and $l \geq \max \{ k + 3, 8 \}$ . This result completes a classification of the primitive base 2 actions of the symmetric groups. During the proof we show that there exists a $k$ -regular bipartite graph $\mathcal{G}$ on $2l$ vertices with no non-trivial automorphisms fixing the bipartite blocks if and only if $k \geq 3$ and $l \geq \max \{ k + 3, 8 \}$ .

For a distribution g over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions g. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where g is the uniform distribution over the k-regular bipartite graphs on W and M. For k = o(n1/4), we establish that L(n)/√kn tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n2 possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γp in probability and in mean when n → ∞.

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in general, but in the near-regular case, i.e., when all the degrees are almost equal, we give a proof of rapid mixing. Our methods also apply to the corresponding problem for general (nonbipartite) regular graphs, which was studied earlier by several researchers. One significant difference in our approach is that our chain has one state for every graph (or bipartite graph) with the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. For the problem of generating tournaments, we are able to prove that our Markov chain on tournaments is rapidly mixing, if the score sequence is near-regular. The proof techniques we use for the two problems are similar. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 293–308, 1999

Let H be a fixed bipartite graph with δ(H) = 1. It is shown that if G is any graph with n vertices and minimum degree at least n/2(1 + on(1)) and e(H) divides e(G), then G can be decomposed into e(G)/e(H) edge-disjoint copies of H. This is best possible and significantly extends the result of an earlier paper by the author [8] which deals with the case where H is a tree.

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. © 1993 John Wiley & Sons, Inc.

A new characterization of maximum matchings for bipartite graphs is presented. It is based on “strong spanning trees” and permits the development of a new algorithm that does not use the classical notion of augmenting paths and that runs in O(|V| |E|) time for bipartite graphs with |V| nodes and |E| edges.