Search

We consider the symmetric difference of two graphs on the same vertex set [n], which is the graph on [n] whose edge set consists of all edges that belong to exactly one of the two graphs. Let F be a class of graphs, and let MF(n) denote the maximum possible cardinality of a family G of graphs on [n] such that the symmetric difference of any two members in G belongs to F. These concepts have been recently investigated by Alon et al. [SIAM J. Discrete Math., 37 (2023), pp. 379-403] with the aim of providing a new graphic approach to coding theory. In particular, MF(n) denotes the maximum possible size of this code. Existing results show that as the graph class F changes, MF(n) can vary from n to 2(1+0(1))(2n). We study several phase transition problems related to MF(n) in general settings and present a partial solution to a recent problem posed by Alon et al. [ABSTRACT FROM AUTHOR]

We prove that every family of (not necessarily distinct) even cycles D1,...D⌊1.2(n-1)⌋+1 on some fixed n-vertex set has a rainbow even cycle (that is, a set of edges from distinct Di's, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer n. [ABSTRACT FROM AUTHOR]

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single-exponential function of k. As a corollary, we prove that the problem ISOMETRIC PATH COVER WITH TERMINALS (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem STRONG GEODETIC SET WITH TERMINALS (which, given a graph G and a set of k terminals, asks whether there exist (2k) shortest paths covering G, each joining a distinct pair of terminals). Moreover, this implies that the related problems ISOMETRIC PATH COVER and STRONG GEODETIC SET (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k. [ABSTRACT FROM AUTHOR]

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate Ω(ε(log(1/∈)+1) that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist (1-ε,l,O(l/ε)) -list-recoverable RS codes with rate Ω(εl√(log(1/ε)+1)) . Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable. [ABSTRACT FROM AUTHOR]

The circumference of a graph G with at least one cycle is the length of a longest cycle in G. A classic result of Birmel\'e [J. Graph Theory, 43 (2003), pp. 24--25] states that the treewidth of G is at most its circumference minus 1. In case G is 2-connected, this upper bound also holds for the pathwidth of G; in fact, even the treedepth of G is upper bounded by its circumference (Bria\'nski et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659--664]). In this paper, we study whether similar bounds hold when replacing the circumference of G by its cocircumference, defined as the largest size of a bond in G, an inclusionwise minimal set of edges F such that G F has more components than G. In matroidal terms, the cocircumference of G is the circumference of the bond matroid of G. Our first result is the following "dual" version of Birmel'e's theorem: The treewidth of a graph G is at most its cocircumference. Our second and main result is an upper bound of 3k 2 on the pathwidth of a 2-connected graph G with cocircumference k. Contrary to circumference, no such bound holds for the treedepth of G. Our two upper bounds are best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

1959, Erd\H os and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. Here, we study a rainbow version of their theorem, in which one considers k ≥ 1 graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any k ≥ 1. [ABSTRACT FROM AUTHOR]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]

In this paper we prove several results on Ramsey numbers R(H,F) for a fixed graph H and a large graph F, in particular for F = Kn. These results extend earlier work of Erd\H os, Faudree, Rousseau, and Schelp and of Balister, Schelp, and Simonovits on so-called Ramsey sizelinear graphs. Among other results, we show that if H is a subdivision of K4 with at least six vertices, then R(H,F) =O(v(F)+e(F)) for every graph F. We also conjecture that if H is a connected graph with e(H) v(H) (k+1/2)2, then R(H,Kn) = O(nk). The case k = 2 was proved by Erd\H os, Faudree, Rousseau, and Schelp. We prove the case k = 3. [ABSTRACT FROM AUTHOR]

Robinson space is a dissimilarity space (X, d) (i.e., a set X of size n and a dissimilarity d on X) for which there exists a total order < on X such that x < y < z implies that d(x, z) \geq max\{ d(x, y), d(y, z)\}. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of (X, d) (generalizing the notion of a module in graph theory) is a subset M of X which is not distinguishable from the outside of M; i.e., the distance from any point of X \setminus M to all points of M is the same. If p is any point of X, then \{ p\}, and the maximal-by-inclusion mmodules of (X, d) not containing p define a partition of X, called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal O(n²) time. [ABSTRACT FROM AUTHOR]

We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe. In typical clustering applications, these universes consist of points in some metric space. Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular. We then define a connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set. Last, we generalize this correspondence for any hierarchical clustering. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles. The idea of viewing tangles as clusters was first proposed by Diestel and Whittle in 2016 as an approach to image segmentation. [ABSTRACT FROM AUTHOR]

A graph F is Ramsey for a pair of graphs (G,H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G = H, received considerable attention. This led to the open question whether there are connected graphs G and G\prime such that (G,G) and (G' ,G') are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that if T belongs to a certain family of trees, including all nontrivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt K2), where Kt K2 is a complete graph Kt with a single edge attached. [ABSTRACT FROM AUTHOR]

We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising p-spin glass model and (b) finding a large independent set in a sparse Erd\H os-Renyi graph. The following families of algorithms are considered: (a) low-degree polynomials of the input-a general framework that captures many prior algorithms; (b) low-depth Boolean circuits; (c) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm. We show that these families of algorithms cannot have high success probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory (although we consider the search problem as opposed to the decision problem). Our proof uses the fact that these models are known to exhibit a variant of the overlap gap property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions whose objectives are above a certain threshold are either close to or far from each other. The crux of our proof is that the classes of algorithms we consider exhibit a form of stability (noise-insensitivity): a small perturbation of the input induces a small perturbation of the output. We show by an interpolation argument that stable algorithms cannot overcome the OGP barrier. The stability of Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials and Boolean circuits is established using tools from Gaussian and Boolean analysis-namely hypercontractivity and total influence, as well as a novel lower bound for random walks avoiding certain subsets, which we expect to be of independent interest. In the case of Boolean circuits, the result also makes use of Linial--Mansour--Nisan's classical theorem. Our techniques apply more broadly to low influence functions, and we expect that they may apply more generally. [ABSTRACT FROM AUTHOR]

The Caccetta--Häggkvist conjecture (denoted CHC) states that the directed girth (the smallest length of a directed cycle) dgirth(D) of a directed graph D on n vertices is at most... where δ+(D) is the minimum outdegree of D. We consider a version involving all outdegrees, not merely the minimum one, and prove that if D does not contain a sink, then dgirth(D) ≤... In the spirit of a generalization of the CHC to rainbow cycles in [1], this suggests the conjecture that given nonempty sets F1, . . ., Fn of edges of Kn, there exists a rainbow cycle of length at most... We prove a bit stronger result when 1 ≤ | Fi| ≤ 2, thereby strengthening a result of DeVos et al. [J. Graph Theory, 96 (2021), pp. 192--202]. We prove a logarithmic bound on the rainbow girth in the case that the sets Fi are triangles. [ABSTRACT FROM AUTHOR]

This work is a continuation of our previous work [D. M. Ha and H. T. Ngo. Int. J. Math., 34 (2023)], studying the expanding phenomenon in matrices over a finite chain ring with large residue field. A sum-product estimate is proved. It is shown that xy+z+t is a very strong expander, and that x(y + z) and xyz + x are moderate expanders of exponent 13. These results generalize the works of Le and Nguyen (see [J. Number. Theory, 216 (2020), pp. 174--191] and [Discrete Appl. Math., 322 (2022), pp. 166--170]. The solvability in large subsets of the equation xy = z + t is obtained, providing an answer to a question raised by Gyarmati and S\'ark\"ozy [Acta Math. Hungar., 119 (2008), pp. 259--280]. The proofs use spectral graph theory and elementary divisor theory. [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]

Graph centrality measures have found widespread use ranking agents in networks by characterizing their "importance" for the purpose of predicting and managing network outcomes. One major application of such a graph centrality problem is found in decentralized, peer-to-peer networks; in particular, the EigenTrust algorithm for trust management aims to reduce the amount of malware distributed in peer-to-peer networks by using graph centrality as a metric for reputation. This popular scheme has been successfully applied to many different types of peer-to-peer networks. However, the effect malicious agents can have on the reliability of schemes like EigenTrust through overt or covert behavior has not yet been fully investigated. In this work, we analyze vulnerabilities in EigenTrust by extending classical eigenvalue/eigenvector sensitivity theory to the nonsmooth setting, where the presence of nonsmoothness in this problem arises from defense mechanisms built into EigenTrust. This enables us to compute the sensitivity of trust scores to ratings provided by individual agents, revealing vulnerabilities in EigenTrust. Our findings indicate that malicious agents can have a large impact on a network despite having relatively low centrality themselves (i.e., appearing untrustworthy). [ABSTRACT FROM AUTHOR]

Finding coarse representations of large graphs which preserve particular features is important in many fields of study, including clustering, numerical approximation, and the creation of reduced order models. Likewise, preserving spectral properties of the original graph during coarsening is also of particular interest for several domains of study. Our contributions are twofold. First, we generalize previous work on coarsening graphs while preserving eigenvalues of the normalized Laplacian by merging nodes with similar adjacencies, and we show that a similar analysis can be done in the case of the combinatorial Laplacian. We additionally show that when the lifted graph of a coarsening spectrally approximates the original graph, the difference between the edge weights of the graph and the edge weights of the lift depend only on the quality of spectral approximation and the strength of connectivity of the graph. It is then shown that in the case of weighted regular graphs the difference between the edge weights of the graph and the edge weights of the lift are bounded purely by the quality of spectral approximation. [ABSTRACT FROM AUTHOR]

In this paper we take a combinatorial approach to the problem of list-decoding, which allows us to determine the precise relation (up to the exact constant) between the decoding radius, list size, and code rate. We prove a generalized Singleton bound for a given list size, and conjecture that the bound is tight for most Reed--Solomon (RS) codes over large enough finite fields. We also show that the conjecture holds true for list sizes 2 and 3, and as a by product show that most RS codes with a rate of at least 1/9 are list-decodable beyond the Johnson radius. Last, we give the first explicit construction in the literature of such RS codes. The main tools used in the proof are a new type of linear dependency between codewords of a code that are contained in a small Hamming ball, and a surprising connection between list-decoding and the notion of cycle space in graph theory. Both of them are new, and may be of independent interest. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [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]

Given a graph G and a set T = {(si, ti): 1 = i = k} of k pairs, the VERTEX-DISJOINT PATHS (resp. EDGE-DISJOINT PATHS) problems asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P1,P2,...,Pk in G such that Pi connects si to ti for each 1 = i = k. Unlike their undirected counterparts which are FPT (parameterized by k) from Graph Minor theory, both the edge-disjoint and vertex-disjoint versions in directed graphs were shown by Fortune et al. (TCS '80) to be NP-hard for k = 2. This strong hardness for DISJOINT PATHS on general directed graphs led to the study of parameterized complexity on special graph classes, e.g., when the underlying undirected graph is planar. For VERTEX-DISJOINT PATHS on planar directed graphs, Schrijver (SICOMP '94) designed an nO(k) time algorithm which was later improved upon by Cygan et al. (FOCS '13) who designed an FPT algorithm running in 22O(k2) ·nO(1) time. To the best of our knowledge, the parameterized complexity of EDGE-DISJOINT PATHS on planar1 directed graphs is unknown. We resolve this gap by showing that EDGE-DISJOINT PATHS is W[1]-hard parameterized by the number k of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no f(k)· no(k) algorithm for EDGE-DISJOINT PATHS on planar DAGs, where k is the number of terminal pairs, n is the number of vertices and f is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most 2. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property P (such as planarity). We say that G is ε -far from P if one has to remove εdn edges to make it have P . The problem of property testing P was introduced in the seminal work of Benjamini, Schramm, and Shapira (Symposium on the Theory of Computing 2008) that gave a tester with query complexity triply exponential in ε - 1 . Levi and Ron [ACM Trans. Algorithms, 11 (2005), 24 2015] have given the best tester to date, with a quasi-polynomial (in ε - 1 ) query complexity. It remained an open problem to show whether there is a property tester whose query complexity is poly(dε - 1 ), even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity d. poly(ε- 1 ). The previous line of work on (independent of n, two-sided) testers is primarily combinatorial. Our work, on the other hand, employs techniques from spectral graph theory. This paper is a continuation of recent work of the authors (Foundations of Computer Science 2018) analyzing random walk algorithms that find forbidden minors. [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]

In this paper, we use analysis on graphs to study quantitative measures of segregation. We focus on a classical statistic from the geography and urban sociology literature known as Moran's I, which in our language is a score associated to a real-valued function on a graph, computed with respect to a spatial weight matrix such as the adjacency matrix associated to the geographic units that tile a city. Our results characterizing the extremal behavior of II illustrate the important role of the underlying graph structure, especially the degree distribution, in interpreting the score. In addition to the standard spatial weight matrices encoding unit adjacency, we consider the Laplacian L and a doubly-stochastic approximation M. These alternatives allow us to connect II to ideas from Fourier analysis and random walks. We offer illustrations of our theoretical results with a mix of stylized synthetic examples and real geographic/demographic data. [ABSTRACT FROM AUTHOR]

In network theory, the concept of effective resistance is a distance measure on a graph that relates the global network properties to individual connections between nodes. In addition, the Kron reduction method is a standard tool for reducing or eliminating the desired nodes, which preserves the interconnection structure and the effective resistance of the original graph. Although these two graph-theoretic concepts stem from the electric network on an undirected graph, they also have a number of applications throughout a wide variety of other fields. In this study, we propose a generalization of a Kron reduction for directed graphs. Furthermore, we prove that this reduction method preserves the structure of the original graphs, such as the strong connectivity or weight balance. In addition, we generalize the effective resistance to a directed graph using Markov chain theory, which is invariant under a Kron reduction. Although the effective resistance of our proposal is asymmetric, we prove that it induces two novel graph metrics in general strongly connected directed graphs. In particular, the effective resistance captures the commute and covering times for strongly connected weight balanced directed graphs. Finally, we compare our method with existing approaches and relate the hitting probability metrics and effective resistance in a stochastic case. In addition, we show that the effective resistance in a doubly stochastic case is the same as the resistance distance in an ergodic Markov chain. [ABSTRACT FROM AUTHOR]

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an ϵ-spectral sparsifier in sublinear time Õ(√mn/ϵ). This contrasts with the optimal classical complexity Õ(m). We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut. [ABSTRACT FROM AUTHOR]

We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity. [ABSTRACT FROM AUTHOR]

A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel [J. Graph Theory, 99 (2022), pp. 217--230] proved that every 1-planar graph with minimum degree 3 and n \geq 7 vertices has a matching of size at least n+12 7, which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and n \geq 36 vertices has a matching of size at least 3n+4 7, and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel [J. Graph Theory, 99 (2022), pp. 217--230]. [ABSTRACT FROM AUTHOR]

We propose near-optimal overlay networks based on d-regular expander graphs to accelerate decentralized federated learning (DFL) and improve its generalization. In DFL a massive number of clients are connected by an overlay network, and they solve machine learning problems collaboratively without sharing raw data. Our overlay network design integrates spectral graph theory and the theoretical convergence and generalization bounds for DFL. As such, our proposed overlay networks accelerate convergence, improve generalization, and enhance robustness to client failures in DFL with theoretical guarantees. Also, we present an efficient algorithm to convert a given graph to a practical overlay network and maintain the network topology after potential client failures. We numerically verify the advantages of DFL with our proposed networks on various benchmark tasks, ranging from image classification to language modeling using hundreds of clients. [ABSTRACT FROM AUTHOR]

We develop a theory to measure the variance and covariance of probability distributions defined on the nodes of a graph, which takes into account the distance between nodes. Our approach generalizes the usual (co)variance to the setting of weighted graphs and retains many of its intuitive and desired properties. Interestingly, we find that a number of famous concepts in graph theory and network science can be reinterpreted in this setting as variances and covariances of particular distributions. As a particular application, we define the maximum variance problem on graphs with respect to the effective resistance distance, and we characterize the solutions to this problem both numerically and theoretically. We show how the maximum variance distribution is concentrated on the boundary of the graph, and illustrate this in the case of random geometric graphs. Our theoretical results are supported by a number of experiments on a network of mathematical concepts, where we use the variance and covariance as analytical tools to study the (co)occurrence of concepts in scientific papers with respect to the (network) relations between these concepts. [ABSTRACT FROM AUTHOR]

We analyze the performance of membrane filters represented by pore networks using two criteria: (1) total volumetric throughput of filtrate over the filter lifetime and (2) accumulated foulant concentration in the filtrate. We first formulate the governing equations of fluid flow on a general network, and we model transport and adsorption of particles (foulants) within the network by imposing an advection equation with a sink term on each pore (edge) as well as conservation of fluid and foulant volumetric flow rates at each pore junction (network vertex). Such a setup yields a system of partial differential equations on the network. We study the influence of three geometric network parameters on filter performance: (1) average number of neighbors of each vertex, (2) initial total void volume of the pore network, and (3) tortuosity of the network. We find that total volumetric throughput depends more strongly on the initial void volume than on average number of neighbors. Tortuosity, however, turns out to be a universal parameter, leading to almost perfect collapse of all results for a variety of different network architectures. In particular, the accumulated foulant concentration in the filtrate shows an exponential decay as tortuosity increases. [ABSTRACT FROM AUTHOR]

Networks with phase-valued nodal variables are central in modeling several important societal and physical systems, including power grids, biological systems, and coupled oscillator networks. One of the distinctive features of phase-valued networks is the existence of multiple operating conditions corresponding to critical points of an energy function or feasible flows of a balance equation. For networks with phase-valued states it is not yet fully understood how many operating conditions exist, how to characterize them, and how to compute them efficiently. A deeper understanding of feasible operating conditions, including their dependence upon network structures, may lead to more reliable and efficient network systems. This paper introduces flow and elastic network problems on the n-torus and provides a rigorous and comprehensive framework for their study. Based on a monotonicity assumption, this framework localizes the solutions, bounds their number, and leads to an algorithm to compute them. Our analysis is based on a novel winding partition of the n-torus into winding cells, induced by Kirchhoff's angle law for undirected graphs. The winding partition has several useful properties, e.g., each winding cell contains at most one solution. The proposed algorithm is based on a novel contraction mapping and is guaranteed to compute all solutions. Finally, we apply our results to study numerically the active power flow equations in several test cases and estimate the power transmission capacity and congestion of a power network. [ABSTRACT FROM AUTHOR]

Given an edge-colored graph, we say that a subgraph is rainbow if all of its edges have different colors. Let ex(n,H, rainbow-F) denote the maximal number of copies of H that a properly edge-colored graph on n vertices can contain if it has no rainbow subgraph isomorphic to F. We determine the order of magnitude of ex(n,Cs, rainbow-Ct) for all s, t with s ≠ = 3. In particular, we answer a question of Gerbner, Mészáros, Methuku, and Palmer by showing that ex(n,C2k, rainbow-C2k) is θ (nk-1) if k ≥ 3 and Θ (n²) if k = 2. We also determine the order of magnitude of ex(n, Pl, rainbow-C2k) for all k, l ≥ 2, where Pl denotes the path with l edges. [ABSTRACT FROM AUTHOR]

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable; in particular we design a 2O(k2) \cdot n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by Dereniowski, Osula, and Rz?azewski [Theoret. Comput. Sci., 794 (2019), pp. 85-100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358-402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a "global" demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2O(k2) \cdot n time algorithm for the monotone and connected version of the edge search number. [ABSTRACT FROM AUTHOR]

The Weisfeiler--Leman procedure is a widely used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the two-dimensional Weisfeiler--Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given nonisomorphic graphs is at most the dimension required to distinguish nonisomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k ≥ 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler--Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2. [ABSTRACT FROM AUTHOR]

Originally arising in the context of interacting particle systems in statistical physics, dynamical systems and differential equations on networks/graphs have permeated into a broad number of mathematical areas as well as into many applications. One central problem in the field is to find suitable approximations of the dynamics as the number of nodes/vertices tends to infinity, i.e., in the large graph limit. A cornerstone in this context are Vlasov equations (VEs) describing a particle density on a mean-field level. For all-to-all coupled systems, it is quite classical to prove the rigorous approximation by VEs for many classes of particle systems. For dense graphs converging to graphon limits, one also knows that mean-field approximation holds for certain classes of models, e.g., for the Kuramoto model on graphs. Yet, the space of intermediate density and sparse graphs is clearly extremely relevant. Here we prove that the Kuramoto model can be be approximated in the meanfield limit by far more general graph limits than graphons. In particular, our contributions are as follows. (I) We show how to introduce operator theory more abstractly into VEs by considering graphops. Graphops have recently been proposed as a unifying approach to graph limit theory, and here we show that they can be used for differential equations on graphs. (II) For the Kuramoto model on graphs we rigorously prove that there is a VE approximating it in the mean-field sense. (III) This mean-field VE involves a graphop, and we prove the existence, uniqueness, and continuous graphop dependence of weak solutions. (IV) On a technical level, our results rely on designing a new suitable metric of graphop convergence and on employing Fourier analysis on compact abelian groups to approximate graphops using summability kernels. [ABSTRACT FROM AUTHOR]

The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theory of perfect graphs and is further and deeply developed in the context of the Lovász theta function and its equivalent characterizations and variants. The main achievement of this paper is the introduction of a new family of norms, providing upper bounds for the stability number, that are obtained through duality from the norms motivated by Hoffman's lower bound for the chromatic number, and which achieve the (complementary) Lovász theta function at their optimum. As a consequence, our norms make it formal that Hoffman's bound for the chromatic number and the Delsarte-Hoffman ratio bound for the stability number are indeed dual. Further, we show that our new bounds strengthen the convex quadratic bounds for the stability number studied by Luz and Schrijver, and which achieve the Lovász theta function at their optimum. One of the key observations regarding weighted versions of these bounds is that, for any upper bound for the stability number of a graph which is a positive definite monotone gauge function, its gauge dual is a lower bound on the fractional chromatic number, and conversely. Our presentation is elementary and accessible to a wide audience. [ABSTRACT FROM AUTHOR]

Abelian group colorings were first introduced by Jaeger et al. in [J. Combin. Theory Ser. B, 56 (1992), pp. 165--182] as the dual concept of group connectivity of graphs. For given groups $\Gamma_1$ and $\Gamma_2$ with $|\Gamma_1| = |\Gamma_2|$, the dual version of a problem raised by Jaeger et al. suggests to investigate whether every $\Gamma_1$-colorable graph $G$ is also $\Gamma_2$-colorable. Recently, Husek, Mohelníková, and Šámal [J. Graph Theory, 93 (2019), pp. 317--327] used computer testing to find the first examples of $\mathbb{Z}_4$-connected but not $\mathbb{Z}_2^2$-connected graphs as well as $\mathbb{Z}_2^2$-connected but not $\mathbb{Z}_4$-connected graphs. As their examples are nonplanar, the group coloring problem remains unanswered. Group coloring was extended to non-abelian groups in Li and Lai [Discrete Math., 313 (2013), pp. 101--104]. We introduce a group coloring local structure (defined as a snarl in the paper) and use it to construct infinitely many ordered triples $(G, \Gamma_1, \Gamma_2)$ in which $G$ is a graph and $\Gamma_1$ and $\Gamma_2$ are groups with $|\Gamma_1| = |\Gamma_2|$, such that $G$ is $\Gamma_1$-colorable but not $\Gamma_2$-colorable. [ABSTRACT FROM AUTHOR]

Complex systems, composed at the most basic level of units and their interactions, describe phenomena in a wide variety of domains, from neuroscience to computer science and economics. The wide variety of applications has resulted in two key challenges: the generation of many domain-specific strategies for complex systems analyses that are seldom revisited, and the compartmentalization of representation and analysis ideas within a domain due to inconsistency in complex systems language. In this work we propose basic, domain-agnostic language in order to advance toward a more cohesive vocabulary. We use this language to evaluate each step of the complex systems analysis pipeline, beginning with the system under study and data collected, then moving through different mathematical frameworks for encoding the observed data (i.e., graphs, simplicial complexes, and hypergraphs), and relevant computational methods for each framework. At each step we consider different types of dependencies; these are properties of the system that describe how the existence of an interaction among a set of units in a system may affect the possibility of the existence of another relation. We discuss how dependencies may arise and how they may alter the interpretation of results or the entirety of the analysis pipeline. We close with two real-world examples using coauthorship data and email communications data that illustrate how the system under study, the dependencies therein, the research question, and the choice of mathematical representation influence the results. We hope this work can serve as an opportunity for reflection for experienced complex systems scientists, as well as an introductory resource for new researchers. [ABSTRACT FROM AUTHOR]

The control of bilinear systems has attracted considerable attention in the field of systems and control for decades, owing to their prevalence in diverse applications across science and engineering disciplines. Although much work has been conducted on analyzing controllability properties, the most used tool remains the Lie algebra rank condition. In this paper, we develop alternative approaches based on theory and techniques in combinatorics to study controllability of bilinear systems. The core idea of our methodology is to represent vector fields of a bilinear system by permutations or graphs, so that Lie brackets are represented by permutation multiplications or graph operations, respectively. Following these representations, we derive combinatorial characterization of controllability for bilinear systems, which consequently provides novel applications of symmetric group and graph theory to control theory. Moreover, the developed combinatorial approaches are compatible with Lie algebra decompositions, including the Cartan and nonintertwining decomposition. This compatibility enables the exploitation of representation theory for analyzing controllability, which allows us to characterize controllability properties of bilinear systems governed by semisimple and reductive Lie algebras. [ABSTRACT FROM AUTHOR]

We consider the pattern detection problem in graphs: given a constant size pattern graph H and a host graph G, determine whether G contains a subgraph isomorphic to H. We present the following new improved upper and lower bounds: We prove that if a pattern H contains a k-clique subgraph, then detecting whether an n node host graph contains a not necessarily induced copy of H requires at least the time for detecting whether an n node graph contains a k-clique. The previous result of this nature required that H contains a k-clique which is disjoint from all other k-cliques of H. We show that if the famous Hadwiger conjecture from graph theory is true, then detecting whether an n node host graph contains a not necessarily induced copy of a pattern with chromatic number t requires at least the time for detecting whether an n node graph contains a t-clique. This implies that (1) under Hadwiger's conjecture for every k-node pattern H, finding an induced copy of H requires at least the time of √k-clique detection and size ω(n√k/4) for any constant depth circuit, and (2) unconditionally, detecting an induced copy of a random G(k, p) pattern with high probability requires at least the time of Θ(k/ log k)-clique detection, and hence also at least size nΩ(k/ log k) for circuits of constant depth. We show that for every k, there exists a k-node pattern that contains a k - 1-clique and that can be detected as an induced subgraph in n node graphs in the best known running time for k -1-clique detection. Previously such a result was only known for infinitely many k. Finally, we consider the case when the pattern is a directed cycle on k nodes, and we would like to detect whether a directed m-edge graph G contains a k-cycle as a not necessarily induced subgraph. We resolve a 14-year-old conjecture of [Yuster and Zwick, Proceedings of SODA, 2004, pp. 247-253] on the complexity of k-cycle detection by giving a tight analysis of their k-cycle algorithm. Our analysis improves the best bounds for k-cycle detection in directed graphs for all k > 5. [ABSTRACT FROM AUTHOR]

Given an n-vertex graph H with minimum degree at least dn for some fixed d > 0, the distribution H\cup G(n, p) over the supergraphs of H is referred to as a (random) perturbation of H. We consider the distribution of edge-colored graphs arising from assigning each edge of the random perturbation H\cup G(n, p) a color, chosen independently and uniformly at random from a set of colors of size r := r(n). We prove that edge-colored graphs which are generated in this manner asymptotically almost surely admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies p := p(n)\geq C/n for some fixed C > 0 and r = (1 + o(1))n. The number of colors used is clearly asymptotically best possible. In particular, this improves on a recent result of Anastos and Frieze [J. Graph Theory, 92 (2019), pp. 405--414] in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-colored sparse pseudorandom graphs asymptotically almost surely admit an almost spanning rainbow path. [ABSTRACT FROM AUTHOR]

The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universalalgebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky--Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ѡ-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. [ABSTRACT FROM AUTHOR]

Exponential family random graph models (ERGMs) are widely used to model networks by parameterizing graph probability in terms of a set of user-selected sufficient statistics. Equivalently, ERGMs can be viewed as expressing a probability distribution on graphs arising from the action of competing social forces that make ties more or less likely, depending on the state of the rest of the graph. Such forces often lead to a complex pattern of dependence among edges, with nontrivial large-scale structures emerging from relatively simple local mechanisms. While this provides a powerful tool for probing macro-micro connections, much remains to be understood about how local forces shape global outcomes. One very simple question of this type is that of the conditions needed for social forces to stabilize a particular structure: that is, given a specific structure and a set of alternatives (e.g., arising from small perturbations), under what conditions will said structure remain more probable than the alternatives? We refer to this property as local stability and seek a general means of identifying the set of parameters under which a target graph is locally stable with respect to a set of alternatives. Here, we provide a complete characterization of the region of the parameter space inducing local stability, showing it to be the interior of a convex cone whose faces can be derived from the change scores of the sufficient statistics vis-\à-vis the alternative structures. As we show, local stability is a necessary but not sufficient condition for more general notions of stability, the latter of which can be explored more efficiently by using the "stable cone" within the parameter space as a starting point. In addition to facilitating the understanding of model behavior, we show how local stability can be used to determine whether a fitted model implies that an observed structure would be expected to arise primarily from the action of social forces, versus by merit of the model permitting a large number of high probability structures, of which the observed structure is one (i.e., entropic effects). We also use our approach to identify the dyads within a given structure that are the least stable, and hence predicted to have the highest probability of changing under the current social forces. The utility of the "stable cone" for ERGM parameter optimization is then demonstrated on a physical model of amyloid fibril formation. This demonstration features a visualization of the stable region, whereby it is shown that the majority of the region of the model's parameter space where ERGM simulations produce the highest fibril yield lies within the "stable cone. [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]

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]

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability distributions. Apart from establishing basic results, we introduce a natural operation called pinning on the space of limit objects and show how this operation yields a canonical cut metric approximation to a given probability distribution akin to the weak regularity lemma for graphons. We also establish the cut metric continuity of basic operations such as taking product measures. [ABSTRACT FROM AUTHOR]