Abstract. Kőnig’s theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of Kőnig’s theorem is that in every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic components needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text]. We prove the following strengthening of Kőnig’s theorem: In every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text].

Abstract. Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.

In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezáková and Dani [15] showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko [12]. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell [26] for finding perfect matchings in certain hypergraphs. Our main innovation in this paper is to introduce the use of topological methods, to replace the combinatorial argument of [26] for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. We also study the (1, ε)-restricted version, in which resources can take only two values, and improve the integrality gap in most cases. Our approach applies a criterion of Aharoni and Haxell, and Meshulam, for the existence of independent transversals in graphs, which involves the connectedness of the independence complex. This is complemented by a graph process of Meshulam that decreases the connectedness of the independence complex in a controlled fashion and hence, tailored appropriately to the problem, can verify the criterion. In our applications we aim to establish the flexibility of the approach and hence argue for it to be a potential asset in other optimization problems involving hypergraph matchings.

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this article, we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph with a given vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this paper we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that BGP is trying to solve is the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution, and so BGP can fail to converge. We define a fractional version of SPP and show that all instances of fractional SPP have solutions. We also show that there are polynomial time reductions from a number of well-known graph problems to SPP. For example, finding stable matchings in hypergraphic preference systems (a generalization of graph stable matchings to the case of hypergraphs) and computing kernels in directed graphs are both polynomial time reducible to SPP. These reductions remain valid in the fractional case. Thus the existence of a polynomial time algorithm for computing fractional solutions to SPP would imply polynomial time algorithms for fractional solutions to these other problems as well.

Extending the Szemerédi regularity lemma for graphs, P. Frankl and V. Rödl [Random Structures Algorithms, 20 (2002), pp. 131–164] established a 3-graph regularity lemma triple systems ${\cal G}_n$ admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion counting lemma [B. Nagle and V. Rödl, Random Structures Algorithms, 23 (2003), pp. 264–332] allowing one to find and enumerate subhypergraphs of a given isomorphism type in a “dense and regular” environment created by the 3-graph regularity lemma. Combined applications of these lemmas are known as the 3-graph regularity method. In this paper, we provide an algorithmic version of the 3-graph regularity lemma which, as we show, is compatible with a counting lemma. We also discuss some applications.

Extending the Szemeredi Regularity Lemma for graphs, P. Frank and Rodl [2002] stablished a 3-graph Regularity Lemma guaranteeing that all large triple systems admit partitions of their edge sets into constantly many classes where most classes consist of regularly distributed edges. Many applications of this lemma require a companion Counting Lemma [Nagle and Rodl, 2003] allowing one to estimate the number of copies of K/sub k//sup 3/ in a "dense and regular" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. For general k-uniform hypergraphs, Regularity and Counting Lemmas were recently established by Gowers [2005] and by Nagle et al., [2005]. We believe the arguments here provide a basis toward a general algorithmic hypergraph regularity method.

The average degree of a subgraph H of the r-dimensional hypercube $Q_r$ equals at most the maximum Hamming distance of any two nodes in H. A corollary is that the minimum number of edges to delete from $Q_r$ such that any two nodes at Hamming distance $\ell$ are separated is $(r+1-\ell) 2^{r-1}$. This corollary has applications to multicommodity flows.