Search

We consider the control of decentralized learning dynamics for agents in an anticoordination network game. In the anticoordination network game, there is a preferred action in the absence of neighbors' actions, and the utility an agent receives from the preferred action decreases as more of its neighbors select the preferred action, potentially causing the agent to select a less desirable action. The decentralized dynamics that are based on the synchronous best-response dynamics converge for the considered payoffs. Given a convergent action profile, we measure anticoordination by the number of edges in the underlying graph that have at least one agent in either end of the edge not taking the preferred action. A designer wants to find an optimal set of agents to control under a finite budget in order to achieve maximum anticoordination (MAC) on game convergence as a result of the dynamics. We show that the MAC is submodular in expectation over all realizations of the payoff interaction constants in bipartite networks. The proof relies on characterizing well-behavedness of MAC instances for bipartite networks, and designing a coupling between the dynamics and another distribution preserving selection protocol, for which we can show the diminishing returns property. Utilizing this result, we obtain a performance guarantee for the greedy optimization of MAC. Finally, we provide a computational study to show the effectiveness of greedy node selection strategies to solve MAC on general bipartite networks. [ABSTRACT FROM AUTHOR]

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Our method is based on a simple and versatile algorithm for computing a Hamilton path on the skeleton of a 0/1-polytope conv(X), where X ⊆ {0, l}n. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem min{w⋅x; | x ∈ X}, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is larger than the running time of the optimization algorithm only by a factor of log n. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations; i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets, and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope, and order polytope, respectively. As another corollary from our framework, we obtain an O(tLPlog n) delay algorithm for the vertex enumeration problem on 0/1-polytopes {x ∈ ℝn | Ax ≤ b}, where A ∈ ℝm x n and b ∈ ℝm, and tLP is the time needed to solve the linear program min{w⋅x | Ax ≤ b}. This improves upon the 25-year-old O(tLP n) delay algorithm due to Bussieck and Lübbecke. [ABSTRACT FROM AUTHOR]

We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analyzing the complexity for restricted patterns and restricted hosts. Specifically, we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time f(H) ⋅ |G|O(1) for some computable function f. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes Q as our central objects of study and establish the following crisp dichotomies as consequences of the exponential time hypothesis: (1) Counting k-matchings in a graph G ∈ Q is fixed-parameter tractable if and only if Q is nowhere dense. (2) Counting k-independent sets in a graph G ∈ Q is fixed-parameter tractable if and only if Q is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if Q is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting k-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in F-colorable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting k-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time, our proofs are much simpler: using structural characterizations of somewhere dense graphs, we show that a colorful version of a recent breakthrough technique for analyzing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting. [ABSTRACT FROM AUTHOR]

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H 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. [ABSTRACT FROM AUTHOR]

We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by Kündgen and Ramamurthi [J. Combin. Theory Ser. B, 85 (2002), pp. 307-337] for the projective planar case. [ABSTRACT FROM AUTHOR]

A graph G is called C2k+1-free if it does not contain any cycle of length 2k + 1. In 1962, Erdös (together with Gallai), and independently Andrásfai, proved that every n-vertex triangle-free graph with more than (n-1)²/4 + 1 edges is bipartite. In this paper, we extend their result and show that for 1 ≤ t 2k - 2 and 2 ≥ 318²k, every n-vertex C2k+1-free graph with more than (n-t-1)²/4 + (t+2) edges can be made bipartite by either deleting at most t - 1 vertices or deleting at most (⌊t-2⌋/2) + (⌈t+2⌉/2) - 1 edges. The construction shows that this is best possible. [ABSTRACT FROM AUTHOR]

Let G = (A ∪ B, E) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching M in G is a popular max-matching if there is no maximum matching more popular than M. In other words, for any maximum matching N, the number of nodes that prefer M to N is at least the number of nodes that prefer N to M. It is known that popular max-matchings always exist in G and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function c : E → R, and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching. [ABSTRACT FROM AUTHOR]

We construct explicit combinatorial Bernoulli factories for the following class of flowbased polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and k-flows. In the process, we uncover new connections to algebraic combinatorics. [ABSTRACT FROM AUTHOR]

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a "small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in a running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a "random looking" graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t). nc, where f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in n (i.e., n (1)). In particular, given constants d > c 1, we output a bipartite graph that has n left nodes and nc right nodes with right-degree of d so that any right set of size at most n (1) expands by factor of (d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and lowdensity parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [SIAM J. Comput., 36 (2006), pp. 845-888] and Ishai et al. [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433-442]). [ABSTRACT FROM AUTHOR]

We correct an error in the appendix of [N. Alon et al., SIAM J. Discrete Math., 34 (2020), pp. 885-903] and prove that it is NP-hard to approximate the size of a maximum induced matching of a bipartite graph within any constant factor. [ABSTRACT FROM AUTHOR]

We consider the asymptotic behavior of the expectation of the maximum for a special assignment process with constant or i.i.d. coefficients. We show how this expectation depends on the coefficients' distribution. [ABSTRACT FROM AUTHOR]

The celebrated dependent random choice lemma states that in a bipartite graph, an average vertex (weighted by its degree) has the property that almost all small subsets S in its neighborhood have a common neighborhood almost as large as in the random graph of the same edge-density. There are two well-known applications of this lemma. The first is a theorem of F\"uredi [Combinatorica, 11 (1991), pp. 75--79] and Alon, Krivelevich, and Sudakov [Combin. Probab. Comput., 12 (2003), pp. 477--494] showing that the maximum number of edges in an n-vertex graph not containing a fixed bipartite graph with maximum degree at most r on one side is O(n2-1/r). This was recently extended by Grzesik, Janzer, and Nagy [J. Combin. Theory Ser. B, 156 (2022), pp. 299--309] to the family of so-called (r, t)-blowups of a tree. A second application is a theorem of Conlon, Fox, and Sudakov [Geom. Funct. Anal., 20 (2010), pp. 1354--1366], confirming a special case of a conjecture of Erd\H os and Simonovits and of Sidorenko, showing that if H is a bipartite graph that contains a vertex that is completely joined to the other part and G is a graph, then the probability that the uniform random mapping from V (H) to V (G) is a homomorphism is at least.... In this paper, we introduce a nested variant of the dependent random choice lemma, which might be of independent interest. We then apply it to obtain a common extension of the theorem of Conlon, Fox, and Sudakov and the theorem of Grzesik, Janzer, and Nagy regarding Tur\'an and Sidorenko properties of so-called tree-degenerate graphs. [ABSTRACT FROM AUTHOR]

Thomassen [J. Combin. Theory Ser. B, 141 (2020), pp. 343--351] asked whether every r-edge-connected r-regular graph of even order has r 2 pairwise disjoint perfect matchings. We show that this is not the case if r = 2 mod 4. Together with a recent result of Mattiolo and Steffen [J. Graph Theory, 99 (2022), pp. 107--116] this solves Thomassen's problem for all even r. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan--Raspaud conjecture, the Berge--Fulkerson conjecture, and the 5-cycle double cover conjecture. [ABSTRACT FROM AUTHOR]

We introduce the first two-way coupled model for the thermo-viscous damping of a mechanical structure (such as quartz tuning fork) that is forced by the weak acoustic and thermal waves generated when a laser source periodically interacts with a trace gas. The model is based on a Helmholtz system of thermo-visco-acoustic equations in the fluid, together with a system of equations for the temperature and the displacement of the structure. These two subsystems are coupled across the fluid-structure interface via several conditions. With this model, the user specifies the geometry of the structure and the viscous and thermal parameters of the fluid, and the model outputs an effective damping parameter and a signal strength that is proportional to the concentration of the trace gas. This new model is a significant improvement over existing one-way coupled models in which damping effects are incorporated via a priori laboratory measurements. Analytical solutions derived for an annular structure show reasonable agreement between the one-way and two-way coupled models at higher ambient pressures. However, at low ambient pressure the one-way coupled model does not adequately capture thermo-viscous effects. [ABSTRACT FROM AUTHOR]

Let Θk1,...,kℓ denote the generalized theta graph, which consists of ℓ internally disjoint paths with lengths k1,...,kℓ, connecting two fixed vertices. We estimate the corresponding extremal number ex(n,Θk1,...,kℓ). When the lengths of all paths have the same parity and at most one path has length 1, ex(n,Θk1,...,kℓ) is O(n1+1/k*), where 2k∗ is the length of the smallest cycle in Θk1,...,kℓ. We also establish matching lower bound in the particular case of ex(n,Θ3,5,5). [ABSTRACT FROM AUTHOR]

A circular r-coloring of a signed graph (G,σ) is an assignment ϕ of points of a circle Cr of circumference r to the vertices of (G,σ) such that for each positive edge uv of (G,σ) the distance of ϕ(v) and ϕ(v) is at least 1 and for each negative edge uv the distance of ϕ(u) from the antipodal of ϕ(v) is at least 1. The circular chromatic number of (G,σ), denoted χc(G,σ), is the infimum of r such that (G,σ) admits a circular r-coloring. This notion is recently defined by Naserasr, Wang, and Zhu who, among other results, proved that for any signed d-degenerate simple graph G^ we have χc(G^)≤2d. For d≥3, examples of signed d-degenerate simple graphs of circular chromatic number 2d are provided. But for d=2 only examples of signed 2-degenerate simple graphs of circular chromatic number close enough to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If (G,σ) is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then χc(G,σ)≤165. Motivated by this observation, we provide an improved upper bound of 4-2⌊n+12⌋ for the circular chromatic number of a signed 2-degenerate simple graph on n vertices and an improved upper bound of 4-4⌊n+22⌋ for the circular chromatic number of a signed bipartite planar simple graph on n vertices. We then show that each of the bounds is tight for any value of n≥4. [ABSTRACT FROM AUTHOR]

Denote by qn (G) the smallest eigenvalue of the signless Laplacian matrix of an n-vertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) =4n/25 · We prove a stronger result: If G is a triangle-free graph, then qn(G) = 15n/94 < 4n/25 Brandt's conjecture is a subproblem of two famous conjectures of Erdőos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n\2] spanning at most n²/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n²/25 edges. In our proof we use linear algebraic methods to upper bound qn(G) by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras. [ABSTRACT FROM AUTHOR]

Recently, the saturation problem of 0-1 matrices has gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this, we initiate the study of the saturation problem of ordered and cyclically ordered graphs. We prove that dichotomy also holds in these two cases, i.e., for a (cyclically) ordered graph its saturation function is either bounded or linear. We also determine the order of magnitude for large classes of (cyclically) ordered graphs, giving infinitely many examples exhibiting both possible behaviors, answering a problem of P\'alv\"olgyi. In particular, in the ordered case we define a natural subclass of ordered matchings, the class of linked matchings, and we start their systematic study, concentrating on linked matchings with at most three links and prove that many of them have bounded saturation function. In both the ordered and cyclically ordered case we also consider the semisaturation problem, where dichotomy holds as well and we can even fully characterize the graphs that have bounded semisaturation function. [ABSTRACT FROM AUTHOR]

Let b(k,ℓ,θ) be the maximum number of vertices of valency k in a (k,ℓ) -semiregular bipartite graph with second-largest eigenvalue θ. We obtain an upper bound for b(k,ℓ,θ) for ..... This bound is tight when there exists a distance-biregular graph with particular parameters, and we develop the necessary properties of distance-biregular graphs to prove this. [ABSTRACT FROM AUTHOR]

Let D=(V,A) be a digraph of order n. We define the degree of vertex v in D to be dD(v)=d+D(v)+d-D(v), where d+D(v) and d-D(v) are the out-degree and in-degree of v in D, respectively. Let k be a positive integer and let W be any given subset of V with |W|≥2k. In this paper we show that if dD(x)+dD(y)≥3n-3 for all {x,y}⊆W, then for any integer partition |W|=∑ki=1ni with ni≥2 for each i, there are k disjoint cycles containing exactly n1,...,nk vertices of W, respectively. The degree condition dD(x)+dD(y)≥3n-3 is sharp in some sense and this result confirms the conjecture posed by Wang [J. Graph Theory, 34 (2000), pp. 154-162] as a corollary. The result in this paper implies a theorem on cycle-factors containing matchings in bipartite graphs. Further, the special case W=V is a directed version of the Aigner-Brandt theorem on disjoint cycles in graphs. [ABSTRACT FROM AUTHOR]

For two graphs G and H, write G rbw \rightarrow H if G has the property that every proper coloring of its edges yields a rainbow copy of H. We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form G \cup G(n, p), where G is an n-vertex graph with edge-density at least d, and d is a constant that does not depend on n. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property G \cup G(n, p) rbw \rightarrow Ks for every s. In this paper, we show that for s \geq 9 the threshold is n 1/m2(K\lceil s/2\rceil); in fact, our 1-statement is a supersaturation result. This turns out to (almost) be the threshold for s = 8 as well, but for every 4 \leq s \leq 7, the threshold is lower; see our companion paper for more details. Also in this paper, we determine that the threshold for the property G \cup G(n, p) rbw \rightarrow C2\ell 1 is n 2 for every \ell \geq 2; in particular, the threshold does not depend on the length of the cycle C2\ell 1. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, G rbw \rightarrow H always holds, whenever G is as above and H is bipartite. [ABSTRACT FROM AUTHOR]

An identifying code C of a graph G is a dominating set of G such that any two distinct vertices of G have distinct closed neighborhoods within C. These codes have been widely studied for over two decades. We give an improvement over all the best known upper bounds, some of which have stood for over 20 years, for identifying codes in trees, proving the upper bound of (n + \ell)/2, where n is the order and \ell is the number of leaves (pendant vertices) of the graph. In addition to being an improvement in size, the new upper bound is also an improvement in generality, as it actually holds for bipartite graphs having no twins (pairs of vertices with the same closed or open neighborhood) of degree 2 or greater. We also show that the bound is tight for an infinite class of graphs and that there are several structurally different families of trees attaining the bound. We then use our bound to derive a tight upper bound of 2n/3 for twin-free bipartite graphs of order n and characterize the extremal examples as 2-corona graphs of bipartite graphs. This is the best possible, as there exist twin-free graphs, and trees with twins, that need n 1 vertices in any of their identifying codes. We also generalize the existing upper bound of 5n/7 for graphs of order n and girth at least 5 when there are no leaves to the upper bound 5n+2\ell 7 when leaves are allowed. This is tight for the 7-cycle C7 and for all stars. [ABSTRACT FROM AUTHOR]

We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]

We consider the asymptotic behavior of the expectation of the maximum for a special assignment process with constant or i.i.d. coefficients. We show how this expectation depends on the coefficients' distribution. [ABSTRACT FROM AUTHOR]

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of maximal bipartite subgraphs, maximal k-degenerate subgraphs (for bounded k), maximal induced chordal subgraphs, and maximal induced trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or \supergraph," and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential; we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met. [ABSTRACT FROM AUTHOR]

This paper considers a special class of nonlocal games (G, ψ), where G is a two-player one-round game, and ψ is a bipartite state independent of G. In the game (G, ψ), the players are allowed to share arbitrarily many copies of ψ. The value of the game (G, ψ), denoted by ω∗(G, ψ), is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states ψ. For a noisy maximally entangled state ψ, a two-player one-round game G and an arbitrarily small precision ϵ > 0, this paper proves an upper bound on the number of copies of ψ for the players to win the game with a probability ϵ close to ω∗(G, ψ). A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than 1. In particular, it includes... [ABSTRACT FROM AUTHOR]

For a graph $G$, $L(G)^t$ is the $t$th power of the line graph of $G$; that is, vertices of $L(G)^t$ are edges of $G$ and two edges $e,f\in E(G)$ are adjacent in $L(G)^t$ if $G$ contains a path with at most $t$ vertices that starts in a vertex of $e$ and ends in a vertex of $f$. The distance-$t$ chromatic index of $G$ is the chromatic number of $L(G)^t$, and a $t$-strong clique in $G$ is a clique in $L(G)^t$. Finding upper bounds for the distance-$t$ chromatic index and $t$-strong clique are problems related to two famous problems: the conjecture of Erdös and Nešetřil concerning the strong chromatic index, and the degree/diameter problem. We prove that the size of a $t$-strong clique in a graph with maximum degree $\Delta$ is at most $1.75\Delta^t+O\left(\Delta^{t-1}\right)$, and for bipartite graphs the upper bound is at most $\Delta^t+O\left(\Delta^{t-1}\right)$. As a corollary, we obtain upper bounds of $1.881\Delta^t +O\left(\Delta^{t-1}\right)$ and $1.9703+O\left(\Delta^{t-1}\right)$ on the distance-$t$ chromatic index of bipartite graphs and general graphs. We also show results for some special classes of graphs: $K_{1,r}$-free graphs and graphs with a large girth. [ABSTRACT FROM AUTHOR]

Gauging the distance between a mixed state and the convex set of separable states in a bipartite quantum mechanical system over the complex field is an important but challenging task. As a first step toward this difficult problem, this paper investigates the rank-1 approximation of a bipartite system over the real field where the entanglement is characterized in terms of the Kronecker product of density matrices. The approximation is recast in the form of a nonlinear eigenvalue problem and a nonlinear singular value problem for which two iterative methods are proposed, respectively. This study offers insight into and might serve as the building block for the more complicated multipartite systems and higher-rank approximation problems. The main focus is on the convergence analysis. Numerical experiments seem to suggest that these easily constructed solvers have higher efficiency when comparing with some state-of-the-art optimization techniques. [ABSTRACT FROM AUTHOR]

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum-cost edge-set to the graph such that the adversary never wins. We show that this problem is equivalent to covering a digraph with nontrivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general nonnegative weights we give tight upper and lower approximation bounds relative to the directed Steiner forest problem. Additionally, we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical strong connectivity augmentation problem as well as directed Steiner problems. [ABSTRACT FROM AUTHOR]

A t-bar visibility representation of a graph assigns each vertex up to t horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least t such that G has a t-bar visibility representation is the bar visibility number of G, denoted by b(G). For the complete bipartite graph Km,n, the lower bound b(Km,n) > [mn+4/2m+2n] from Euler's formula is well known. We prove that equality holds. [ABSTRACT FROM AUTHOR]

In the list coloring problem for two matroids, we are given matroids M1 = (S, \scrI 1) and M2 = (S, \scrI 2) on the same ground set S, and the goal is to determine the smallest number k such that, given arbitrary lists Ls of k colors for s \in S, it is possible to choose a color from each list so that every monochromatic set is independent in both M1 and M2. When both M1 and M2 are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant c such that if the coloring number is k (i.e., the ground set can be partitioned into k common independent sets), then the list coloring number is at most c \cdot k. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if M = (S, \scrI) is a matroid in which S can be partitioned into k independent sets, then there exists a partition matroid N = (S,\scrJ) with \scrJ \subseteq \scrI in which S can be partitioned into (A) k independent sets if M is a transversal matroid, (B) 2k 1 independent sets if M is a graphic matroid, (C) \lceil kr/(r 1)\rceil independent sets if M is a paving matroid of rank r, and (D) 2k 2 independent sets if M is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of N is the same as that of M. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one. [ABSTRACT FROM AUTHOR]

The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It is known that, for all n\geq 8, the balanced complete bipartite 3-uniform hypergraph on n vertices, denoted by Bn, is the 3-uniform hypergraph on n vertices with the largest number of hyperedges that does not contain a copy of the Fano plane. For sufficiently large r and n, we show that Bn admits the largest number of r-edge colorings with no rainbow copy of the Fano plane. [ABSTRACT FROM AUTHOR]

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in K3,3-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this "opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K3,3-free graphs." In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and later by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This family includes several well-studied graph families including the K3,3-minor-free graphs and K5-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as O(n). Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: (1) Determining whether a given graph has a perfect matching and, if so, finding one. (2) Finding a minimum-weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. (3) Finding a maximum st-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same with respect to matching problems involving a fixed set of terminals, as the larger network they replace. [ABSTRACT FROM AUTHOR]

In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109-117; G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717-763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. [ABSTRACT FROM AUTHOR]

We show that the bipartite perfect matching problem is in quasi-NC². That is, it has uniform circuits of quasi-polynomial size nO(log n), and O(log² n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem. [ABSTRACT FROM AUTHOR]

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chv'atal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milaniv c [J. Discrete Algorithms, 6 (2008), pp. 595--604]. [ABSTRACT FROM AUTHOR]

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in Theta (log chi (G)), while for 3D the minimum scan time is not upper bounded by chi (G). We use this relationship to prove that the existence of a constant-factor approximation implies P = NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an O(c)-approximation for k-colored graphs with k leq chi (G)c. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph. [ABSTRACT FROM AUTHOR]

This paper considers an edge minimization problem in saturated bipartite graphs. An n by n bipartite graph G is H-saturated if G does not contain a subgraph isomorphic to H but adding any missing edge to G creates a copy of H. More than half a century ago, Wessel and Bollob'as independently solved the problem of minimizing the number of edges in K(s,t)-saturated graphs, where K(s,t) is the "ordered"" complete bipartite graph with s vertices from the first color class and t from the second. However, the very natural "unordered"" analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When s = t, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Kor'andi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in K(s,t)-saturated n by n bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for s = t 1 with the classification of the extremal graphs. We also improve the estimates of Gan, Kor'andi, and Sudakov for general s and t, and for all sufficiently large n. [ABSTRACT FROM AUTHOR]

We consider the following question. We have a dense regular graph G with degree n, where > 0 is a constant. We add m = o(n2) random edges. The edges of the augmented graph G(m) are given independent edge weights X(e); e 2 E(G(m)). We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph but scaled by a factor -1. We consider spanning trees, shortest paths, and perfect matchings in (pseudorandom) bipartite graphs. [ABSTRACT FROM AUTHOR]

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size t in a bipartite graph G with a fixed bipartition is an independent set with exactly t vertices in each part; in other words, it is a copy of Kt,t in the bipartite complement of G. Let f(n, Delta) be the largest k for which every n times n bipartite graph with maximum degree Delta in one of the parts has a bi-hole of size k. Determining f(n, Delta) is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. It has connections to the bipartite version of the Erd Hos--Hajnal conjecture, bipartite Ramsey numbers, and the Zarankiewicz problem. Our main result determines the asymptotic behavior of f(n, Delta). More precisely, we show that for large but fixed Delta and n sufficiently large, f(n, Delta) = Theta (log Delta Delta n). We further address more specific regimes of Delta, especially when Delta is a small fixed constant. In particular, we determine f(n, 2) exactly and obtain bounds for f(n, 3), though determining the precise value of f(n, 3) is still open. [ABSTRACT FROM AUTHOR]

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with bigl(2k k bigr) steps with generalized rectangles, there is a row or a column in the diagram that is used by at least k + 1 rectangles and prove that this is best possible. This answers two questions by Kim et al. [European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension (1 + o(1)) log2 log2 n. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension. [ABSTRACT FROM AUTHOR]

We prove that every bipartite graph of sufficiently large average degree has either a Kt,t-subgraph or an induced subgraph of average degree at least t and girth at least 6. We conjecture that "6"" can be replaced by any constant "k,"" which strengthens a conjecture of Thomassen. In support of this conjecture, we show that it holds for regular graphs. [ABSTRACT FROM AUTHOR]

A class scrF of graphs has the induced ErdH os--Posa property if there exists a function f such that for every graph G and every positive integer k, G contains either k pairwise vertex-disjoint induced subgraphs that belong to scrF, or a vertex set of size at most f(k) hitting all induced copies of graphs in scrF. Kim and Kwon in [J. Combin. Theory Ser. B, 145 (2020), pp. 65--112] showed that for a cycle Cell of length ell, the class of Cell -subdivisions has the induced ErdH os-Posa property if and only if ell leq 4. In this paper, we investigate whether or not the class of H-subdivisions has the induced ErdH os--P'osa property for other graphs H. We completely settle the case when H is a forest or a complete bipartite graph. Regarding the general case, we identify necessary conditions on H for the class of H-subdivisions to have the induced ErdH os-P'osa property. For this, we provide three basic constructions that are useful for proving that the class of the subdivisions of a graph does not have the induced ErdH os-Posa property. Among remaining graphs, we prove that if H is the diamond, the 1-pan, or the 2-pan, then the class of H-subdivisions has the induced Erd Hos-P'osa property. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a weighted graph or multigraph, with f or b a function assigning a nonnegative integer to each vertex. An f-factor is a subgraph whose degree function is f; a perfect b-matching is a b-factor in the graph formed from G by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum f-factor, i.e., f-factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum f-factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum b-matching, i.e., maximum weight b-matching. It is almost identical to its special case b ≡ 1, ordinary weighted matching. The time is O(Wb(V)ω) for W the maximum magnitude of an edge weight, b(V) = ∑v∈V b(v), and ω < 2:373 the exponent of matrix multiplication. An algebraic algorithm to find an f-factor. The time is O(f(V)ω) for f(V ) = ∑v∈V f(v). The specialization of the f-factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite f-factors. This improves the known complexity bounds for vertex capacitated max- ow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. [ABSTRACT FROM AUTHOR]

We interpret realizations of a graph on the sphere up to rotations as elements of a moduli space of curves of genus zero. We focus on those graphs that admit an assignment of edge lengths on the sphere resulting in a flexible object. Our interpretation of realizations allows us to provide a combinatorial characterization of these graphs in terms of the existence of particular colorings of the edges. Moreover, we determine necessary relations for flexibility between the spherical lengths of the edges. We conclude by classifying all possible motions on the sphere of the complete bipartite graph with 3+3 vertices where no two vertices coincide or are antipodal. [ABSTRACT FROM AUTHOR]

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal. We specifically study graphs that have an ordering avoiding some ordered structures. More precisely, we consider structures that we call patterns on three nodes, and we study the complexity of recognizing the classes associated with such patterns. In this domain, there are three key previous works. Independently Skrien [J. Graph Theory, 6 (1982), pp. 309-316] and Damashke [Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 219--229] noted that several graph classes, such as chordal, bipartite, interval, and comparability graphs, have a characterization in terms of forbidden patterns. On the algorithmic side, Hell, Mohar, and Rafiey [Ordering without forbidden patterns, in Algorithms--ESA 2014, Springer, 2014, pp. 554--565] proved that any class defined by a set of forbidden patterns on three nodes can be recognized in time O(n3) by using an algorithm based on an extension of 2-SAT. We improve on these two lines of works by systematically characterizing all the classes defined by sets of forbidden patterns (on three nodes) and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time. Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of practical fixed-time bipartite consensus of a nonlinear incommensurate fractional-order multiagent system (MAS) in a general coopetition network with signed directed graph, where the signed directed graph is composed of both positive and negative interaction links. By introducing a sliding-mode manifold, the incommensurate fractionalorder MAS is transformed into an integer-order MAS. Then, practical fixed-time bipartite consensus protocols with constant and adaptive gains are designed, respectively, for the obtained integer-order MAS. By artfully constructing a Lyapunov function, it is shown that the practical bipartite consensus can be achieved with a settling time. Moreover, the upper bound of the settling time can be estimated explicitly, which is irrelevant to any initial conditions. Finally, the effectiveness of the proposed practical fixed-time bipartite consensus schemes is illustrated by numerical simulation. [ABSTRACT FROM AUTHOR]

A matrix is homogeneous if all of its entries are equal. Let P be a 2 times 2 zero-one matrix that is not homogeneous. We prove that if an n times n zero-one matrix A does not contain P as a submatrix, then A has a cn times cn homogeneous submatrix for a suitable constant c > 0. We further provide an almost complete characterization of the matrices P (missing only finitely many cases) such that forbidding P in A guarantees an n1 o(1) times n1 o(1) homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs. [ABSTRACT FROM AUTHOR]

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem. [ABSTRACT FROM AUTHOR]

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) Δ-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite Δ-regular tree. We also find efficient counting and sampling algorithms for proper q-colorings of random Δ-regular bipartite graphs when q is sufficiently small as a function of Δ. [ABSTRACT FROM AUTHOR]