Search

Given graphs F and G, a perfect F-tiling in G is a collection of vertex-disjoint copies of F in G that together cover all the vertices in G. The study of the minimum degree threshold forcing a perfect F-tiling in a graph G has a long history, culminating in the Kühn--Osthus theorem [D. Kühn and D. Osthus, Combinatorica, 29 (2009), pp. 65-107] which resolves this problem, up to an additive constant, for all graphs F. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs F this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect P-tiling in an edge-ordered graph, where P is any fixed monotone path. [ABSTRACT FROM AUTHOR]

Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial intelligence, combinatorics, computer science, database theory, and logic. In the present paper, we introduce the subclass of hypergraph Horn functions that generalizes matroids and equivalence relations. We provide multiple characterizations of hypergraph Horn functions in terms of implicate-duality and the closure operator, which are, respectively, regarded as generalizations of matroid duality and the Mac Lane-Steinitz exchange property of matroid closure. We also study algorithmic issues on hypergraph Horn functions and show that the recognition problem (i.e., deciding if a given definite Horn CNF represents a hypergraph Horn function) and key realization (i.e., deciding if a given hypergraph is realized as a key set by a hypergraph Horn function) can be done in polynomial time, while implicate sets can be generated with polynomial delay. [ABSTRACT FROM AUTHOR]

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

Matroids and semigraphoids are discrete structures abstracting and generalizing linear independence among vectors and conditional independence among random variables, respectively. Despite the different nature of conditional independence from linear independence, deep connections between these two areas are found and are still undergoing active research. In this paper, we give a characterization of the embedding of matroids into conditional independence structures and its oriented counterpart, which leads to new axiom systems of matroids and oriented matroids. [ABSTRACT FROM AUTHOR]

In this paper, we strengthen a result by Green about an analogue of Sárközy's theorem in the setting of polynomial rings Fq[x]. In the integer setting, for a given polynomial F ∈ Z[x] with constant term zero, (a generalization of) Sárközy's theorem gives an upper bound on the maximum size of a subset A ⊂{1, ..., n} that does not contain distinct α1, α2 ∈ A satisfying α1, -- α2 = F(b) for some b ∈ Z. Green proved an analogous result with much stronger bounds in the setting of subsets A ⊂ Fq[x] of the polynomial ring Fq[x], but this result required the additional condition that the number of roots of the polynomial F ∈ Fq[x] be coprime to q. We generalize Green's result, removing this condition. As an application, we also obtain a version of Sárközy's theorem with similar strong bounds for subsets A ⊂ Fq for q=pn for a fixed prime p and large n. [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]

The dichromatic number ...(D) of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if ...(D) = k and each proper subgraph D' of D satisfies ...(-D') ≤ k - 1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by Ok(n) the minimum number of edges of a k-dicritical oriented graph on n vertices. The main result of this paper is a proof that O3(n) ≥ 7n+2/3 together with a construction witnessing that O3(n) ≤ ⌈5n/2⌉ for all n ≥ 12. We also give a construction showing that for all sufficiently large n and all k ≥ 3, Ok(n) < (2k -- 3)n, disproving a conjecture of Hoshino and Kawarabayashi. [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]

A Sidorenko bigraph is one whose density in a bigraphon W is minimized precisely when W is constant. Several techniques in the literature to prove the Sidorenko property consist of decomposing (typically in a tree decomposition) the bigraph into smaller building blocks with stronger properties. One prominent such technique is that of N-decompositions of Conlon and Lee, which uses weakly Holder (or weakly norming) bigraphs as building blocks. In turn, to obtain weakly Holder bigraphs, it is typical to use the chain of implications reflection bigraph ⇒ cut-percolating bigraph ⇒ weakly Holder bigraph. In an earlier result by the author with Razborov, we provided a generalization of N-decompositions, called reflective tree decompositions, that uses much weaker building blocks, called induced-Sidorenko bigraphs, to also obtain Sidorenko bigraphs. In this paper, we show that "left-sided" versions of the concepts of reflection bigraph and cut-percolating bigraph yield a similar chain of implications: left-reflection bigraph ⇒ left-cut-percolating bigraph ⇒ induced-Sidorenko bigraph. We also show that under mild hypotheses the "left-sided" analogue of the weakly Holder property (which is also obtained via a similar chain of implications) can be used to improve bounds on another result of Conlon and Lee that roughly says that bigraphs with enough vertices on the right side of each realized degree have the Sidorenko property. [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]

A k-page book drawing of a graph G is a drawing of G on k halfplanes with a line l as a common boundary such that the vertices are located on l and the edges cannot cross l. The k-page book crossing number of the graph G, denoted by Vk (G), is the minimum number of edge-crossings over all k-page book drawings of G. This paper improves previous results on k-page book crossing numbers of the complete graph Kn. We determine Vk (Kn) whenever 2 < n/k ≤ 3 and improve the lower bounds on Vk (Kn) for all k ≥ 14. Our proofs rely on bounding the number of edges in convex geometric graphs with few crossings per edge. [ABSTRACT FROM AUTHOR]

The planar graph product structure theorem of Dujmovi\'c et al. [J. ACM, 67 (2020), 22] states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This result has been the key tool to resolve important open problems regarding queue layouts, nonrepetitive colorings, centered colorings, and adjacency labeling schemes. In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond-planar graph classes. The key observation that drives our work is that many beyond-planar graphs can be described as a shallow minor of the strong product of a planar graph with a small complete graph. In particular, we show that powers of bounded degree planar graphs, k-planar, (k, p)-cluster planar, fan-planar, and k-fan-bundle planar graphs have such a shallow-minor structure. Using a combination of old and new results, we deduce that these classes have bounded queue-number, bounded nonrepetitive chromatic number, polynomial p-centered chromatic numbers, linear strong coloring numbers, and cubic weak coloring numbers. In addition, we show that k-gap planar graphs have at least exponential local treewidth and, as a consequence, cannot be described as a subgraph of the strong product of a graph with bounded treewidth and a path. [ABSTRACT FROM AUTHOR]

Given a metric space \scrM = (X, γ), a weighted graph G over X is a metric t-spanner of scrM if for every u, v \in X, γ(u, v) \leq γG(u, v) \leq t \cdot γ (u, v), where γ G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s1,. . ., sn), where the points are presented one at a time (i.e., after i steps, we see Si = \{ s1, . . ., si\}). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner Gi for Si for all i, while minimizing the number of edges, and their total weight. We construct online (1+ε)-spanners in the Euclidean d-space, (2k 1)(1+ε)-spanners for general metrics, and (2 + ε)-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a (1 + ε)-spanner with competitive ratio O(\varepsilon 3/2 log n 1 log n), bypassing the classic lower bound (ε 2) for lightness, which compares the weight of the spanner to that of the minimum spanning tree. [ABSTRACT FROM AUTHOR]

We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Sol\'e et al. [Adv. Complex Syst., 5 (2002), pp. 43-54] in which the graph grows according to a duplication-divergence mechanism, i.e., by iteratively creating a copy of some node and then randomly alternating the neighborhood of a new node with probability p. This model captures the growth of some real-world processes, e.g., biological or social networks. In this paper, we prove that for some 0 < p < 1, the maximum degree and the average degree of a duplication-divergence graph on t vertices are asymptotically concentrated with high probability around tp and max\{ t2p-1, 1}, respectively, i.e., they are within at most a polylogarithmic factor from these values with probability at least 1-t-A for any constant A >0. [ABSTRACT FROM AUTHOR]

Given a graph G= (V,E) on n vertices and an assignment of colors to its edges, a set of edges S \subseteq E is said to be rainbow if edges from S have pairwise different colors assigned to them. In this paper, we investigate rainbow spanning trees in randomly colored random Gk-out graphs. [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]

In this paper, we study a biased version of the nearest-neighbor transposition Markov chain on the set of permutations where neighboring elements i and j are placed in order (i, j) with probability pi,j. Our goal is to identify the class of parameter sets P = \{ pi,j\} for which this Markov chain is rapidly mixing. Specifically, we consider the open conjecture of Jim Fill [Background on the Gap Problem (2003) and An Interesting Spectral Gap Problem (2003)] that all monotone, positively biased distributions are rapidly mixing. We resolve Fill's conjecture in the affirmative for distributions arising from k-class particle processes, where the elements are divided into k classes and the probability of exchanging neighboring elements depends on the particular classes the elements are in. We further require that k is a constant and that all probabilities between elements in different classes are bounded away from 1/2. These particle processes arise in the context of selforganizing lists, and our result also applies beyond permutations to the setting where all particles in a class are indistinguishable. Our work generalizes recent work by Haddadan and Winkler [Mixing of permutations by biased transposition (2017)] studying 3-class particle processes. Additionally, we show that a broader class of distributions based on trees is also rapidly mixing, which generalizes a class analyzed by Bhakta et al. [Mixing times of Markov chains for self-organizing lists and biased permutations (2013)]. Our proof involves analyzing a generalized biased exclusion process, which is a nearest-neighbor transposition chain applied to a 2-particle system. Biased exclusion processes are of independent interest, with applications in self-assembly. We generalize the results of Greenberg et al. [Sampling biased lattice configurations using exponential metrics (2009)] and Benjamini et al. [Mixing times of the biased card shuffling and the asymmetric exclusion process (2005)] on biased exclusion processes to allow the probability of swapping neighboring elements to depend on the entire system, as long as the minimum bias is bounded away from 1. [ABSTRACT FROM AUTHOR]

Fix k > 0, and let G be a graph, with vertex set partitioned into k subsets ("blocks") of approximately equal size. An induced subgraph of G is "transversal" (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A "pure pair" in G is a pair X,Y of disjoint subsets of V (G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded. [ABSTRACT FROM AUTHOR]

The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a linear programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress toward Wegner's conjecture for distance-2 coloring of planar graphs by showing that 12 colors are sufficient to color at distance 2 every planar graph with maximum degree 4. [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]

The basis exchange axiom has been a driving force in the development of matroid theory. However, the axiom gives only a local characterization of the relation of bases, which is a major stumbling block to further progress, and providing a global understanding of the structure of matroid bases is a fundamental goal in matroid optimization. While studying the structure of symmetric exchanges, Gabow proposed the problem that any pair of bases admits a sequence of symmetric exchanges. A different extension of the exchange axiom was proposed by White, who investigated the equivalence of compatible basis sequences. These conjectures suggest that the family of bases of a matroid possesses much stronger structural properties than we are aware of. In the present paper, we study the distance of basis pairs of a matroid in terms of symmetric exchanges. In particular, we give a polynomial-time algorithm that determines a shortest possible exchange sequence that transforms a basis pair into another for split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. As a corollary, we verify the above-mentioned long-standing conjectures for this large class. As paving matroids form a subclass of split matroids, our result settles the conjectures for paving matroids as well. [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]

A remarkable conjecture of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] asserts that for any collection of n independent nonnegative, where X = Σ ni=1=i. In this paper, we investigate thisconjecture for the class of discrete log-concave probability distributions, and we prove a strengthened version. More specifically, we show that the conjectured bound 1/e holds when Xi's are independent discrete log-concave with arbitrary expectation. [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]

Given a graph G= (V,E) on n vertices and an assignment of colors to its edges, a set of edges S \subseteq E is said to be rainbow if edges from S have pairwise different colors assigned to them. In this paper, we investigate rainbow spanning trees in randomly colored random Gk-out graphs. [ABSTRACT FROM AUTHOR]

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]

It is known that any open necklace with beads of t types, in which the number of beads of each type is divisible by k, can be partitioned by at most (k -- 1)t cuts into intervals that can be distributed into k collections, each containing the same number of beads of each type. This is tight for all values of k and t. Here, we consider the case of random necklaces, where the number of beads of each type is km. Then the minimum number of cuts required for a "fair" partition with the above property is a random variable X(k,t,m). We prove that for fixed k,t and large m, this random variable is at least (k -- 1)(t + 1)/2 with high probability. For k = 2, fixed t, and large m, we determine the asymptotic behavior of the probability that X(2,t,m) = s for all values of s ≤ t. We show that this probability is polynomially small when s < (t + 1)/2, is bounded away from zero when s > (t + 1)/2, and decays like ɵ(1/logm) when s = (t + 1)/2. We also show that for large t, X(2,t,1) is at most (0.4 + o(1))t with high probability and that for large t and large ratio k/logt, X(k,t,1) is o(kt) with high probability. [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]

For a locally finite set, A ⊆ Rd, the kth Brillouin zone of a ∈ A is the region of points x ∈Rd for which ||x -- a|| is the kth smallest among the Euclidean distances between x and the points in A. If A is a lattice, the kth Brillouin zones of the points in A are translates of each other, and together they tile space. Depending on the value of k, they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in R², and the convergence of the maximum volume of a chamber to zero for the integer lattice. [ABSTRACT FROM AUTHOR]

An obstacle representation of a graph G consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n-vertex graph is O(nlogn) [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom., 59 (2018), pp. 143-164] and that there are n-vertex graphs whose obstacle number is Ω(n/(log logn)2) [V. Dujmovic and P. Morin, Electron. J. Combin., 22 (2015), 3.1]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmovic and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n²) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle. [ABSTRACT FROM AUTHOR]

It is proved that the Weisfeiler-Leman dimension of the class of permutation graphs is at most 18. Previously, it was only known that this dimension is finite (B. Grußien, Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, pp. 1-12). [ABSTRACT FROM AUTHOR]

Many important problems in extremal combinatorics can be stated as certifying polynomial inequalities in graph homomorphism numbers, and in particular, many ask to certify pure binomial inequalities. For a fixed collection of graphs IA, the tropicalization of the graph profile of U essentially records all valid pure binomial inequalities involving graph homomorphism numbers for graphs in U. Building upon ideas and techniques described by Blekherman and Raymond in 2022, we compute the tropicalization of the graph profile for the graph containing a single vertex as well as stars where one edge is subdivided. This allows pure binomial inequalities in homomorphism numbers (or densities) for these graphs to be verified through an explicit linear program where the number of variables is equal to the number of edges in the biggest graph involved. [ABSTRACT FROM AUTHOR]

Given a simple Eulerian binary matroid M, what is the minimum number of disjoint circuits necessary to decompose M? We prove that |M|/(rank(M) + 1) many circuits suffice if M = F2n\{0} is the complete binary matroid, for certain values of n, and that O(2rank(M)/(rank(M)+1)) many circuits suffice for general M. We also determine the asymptotic behavior of the minimum number of circuits in an odd-cover of M. [ABSTRACT FROM AUTHOR]

We give an approximate Menger-type theorem for the case when a graph G contains two X-Y paths P1 and P2 such that P1 ∪ P2 is an induced subgraph of G. More generally, we prove that there exists a function f(d) ∈ O(d), such that for every graph G and X,Y ⊆. V(G), either there exist two X-Y paths P1 and P2 such that the distance between P1 and P2 is at least d, or there exists v ∈ V(G) such that the ball of radius f(d) centered at v intersects every X-Y path. [ABSTRACT FROM AUTHOR]

Given a graph H, we say that an edge-colored graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any nonedge in any color creates a rainbow copy of H. The rainbow saturation number rsat(n, H) is the minimum number of edges among all H-rainbow saturated edge-colored graphs on n vertices. We prove that for any nonempty graph H, the rainbow saturation number is linear in n, thus proving a conjecture of Girã, Lewis, and Popielarz. In addition, we give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz. [ABSTRACT FROM AUTHOR]

We define the k-cut complex of a graph G with vertex set V(G) to be the simplicial complex whose facets are the complements of sets of size k in V(G) inducing disconnected subgraphs of G. This generalizes the Alexander dual of a graph complex studied by Fröberg [Topics in Algebra, Part 2, PWN, Warsaw, 1990, pp. 57-70] and Eagon and Reiner [J. Pure Appl. Algebra, 130 (1998), pp. 265-275]. We describe the effect of various graph operations on the cut complex and study its shellability, homotopy type, and homology for various families of graphs, including trees, cycles, complete multipartite graphs, and the prism Kn X K2, using techniques from algebraic topology, discrete Morse theory, and equivariant poset topology. [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]

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]

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]

Let X be a finite set. A family P of subsets of X is called a convex geometry with ground set X if (1) Ø, X ∈ P; (2)O A ∩ B ∈ P whenever A, B ∈ P; and (3) if A ∈ P and A ≠ X, there is an element α ∈ X -- A such that A ∪ {α} ∈ P. As a nonempty family of sets, a convex geometry has a well defined VC-dimension. In the literature, a second paramete, called the convex dimension, has been defined expressly for these structures. Partially ordered by inclusion, a convex geometry is also a poset, and four additional dimension parameters have been defined for this larger class, called the Dushnik--Miller dimension, Boolean dimension, local dimension, and fractional dimension, respectively. For each pair of these six dimension parameters, we investigate whether there is an infinite class of convex geometries on which one parameter is bounded and the other is not. [ABSTRACT FROM AUTHOR]

We prove that the number of tropical critical points of an affine matroid (M, e) is equal to the beta invariant of M. Motivated by the computation of maximum likelihood degrees, this number is defined to be the degree of the intersection of the Bergman fan of (M, e) and the inverted Bergman fan of N = (M/e), where e is an element of M that is neither a loop nor a coloop. Equivalently, for a generic weight vector w on E -- e, this is the number of ways to find weights (0,x) on M and y on N with x + y = w such that, on each circuit of M (resp., N), the minimum x-weight (resp., y-weight) occurs at least twice. This answers a question of Sturmfels. [ABSTRACT FROM AUTHOR]

could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst-case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev., 3 (2009), pp. 65-69], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst-case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links. [ABSTRACT FROM AUTHOR]

We estimate the likely values of the chromatic and independence numbers of the random r-uniform d-regular hypergraph on n vertices for fixed r, large fixed d, and n → ∞. [ABSTRACT FROM AUTHOR]

A homomorphism φ from a guest graph G to a host graph H is locally bijective, injective, or surjective if for every u ∈ V(G), the restriction of φ to the neighbourhood ofu is bijective, injective, or surjective, respectively. We prove a number of new FPT (fixed-parameter tractable), W[1]-hard, and paraNP-complete results for the corresponding decision problems LBHOM, LIHOM, and LSHOM by considering a hierarchy of parameters of the guest graph G. In this way we strengthen several existing results. For our FPT results, we develop a new algorithmic framework that involves a general ILP (integer linear program) model. We also use our framework to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms. [ABSTRACT FROM AUTHOR]

Recently, it was proved by Bérczi and Schwarcz that the problem of factorizing a matroid into rainbow bases with respect to a given partition of its ground set is algorithmically intractable. On the other hand, many special cases were left open. We first show that the problem remains hard if the matroid is graphic, answering a question of Bérczi and Schwarcz. As another special case, we consider the problem of deciding whether a given digraph can be factorized into subgraphs which are spanning trees in the underlying sense and respect upper bounds on the indegree of every vertex. We prove that this problem is also hard. This answers a question of Frank. In the second part of the article, we deal with the relaxed problem of covering the ground set of a matroid by rainbow bases. Among other results, we show that there is a linear function f such that every matroid that can be factorized into k bases for some k ≥ 3 can be covered by f(k) rainbow bases if every partition class contains at most 2 elements. [ABSTRACT FROM AUTHOR]

Tuza [Finite and Infinite Sets, Proc. Colloq. Math. Soc. János Bolyai 37, North Holland, 1981, p. 888] conjectured that τ(G) ≤ 2v(G) for all graphs G, where τ(G) is the minimum size of an edge set whose removal makes G triangle-free and v(G) is the maximum size of a collection of pairwise edge-disjoint triangles. Here, we generalize Tuza's conjecture to simple binary matroids that do not contain the Fano plane as a restriction and prove that the geometric version of the conjecture holds for cographic matroids. [ABSTRACT FROM AUTHOR]

We show that for every r ≥ 3, the maximal running time of the Kr+1r-bootstrap percolation in the complete r-uniform hypergraph on n vertices Knr is ϴ(nr). This answers a recent question of Noel and Ranganathan in the affirmative and disproves a conjecture of theirs. Moreover, we show that the prefactor is of the form r-reO(r) as r → ∞, [ABSTRACT FROM AUTHOR]

For an integer a and a graph G, the a-disintegration of G is the graph obtained from G by recursively deleting vertices of degree at most a until the resulting graph has no such vertex. Pósa proved that if a 2-connected graph contains a path on m ≥ k vertices with end-vertices in its ⌊(k-1)2]⌋disintegration, then G contains a cycle of length at least k. We prove that if a 2-connected graph contains a path on m ≥ k vertices with end-vertices in its ⌊(k-3)/2⌋-disintegration, then G contains either a cycle of length at least k or a specific family of graphs. As an application, we strengthen the Erdös--Gallai stablity theorem of Füredi, Kostochka, Luo, and Verstraëte. [ABSTRACT FROM AUTHOR]

We describe a robust methodology, based on the martingale argument of Nachmias and Peres and random walk estimates, to obtain simple upper and lower bounds on the size of a maximal component in several random graphs at criticality. Even though the main result is not new, we believe the material presented here is interesting because it unifies several proofs found in the literature into a common framework. More specifically, we give easy-to-check conditions that, when satisfied, allow an immediate derivation of the above-mentioned bounds. [ABSTRACT FROM AUTHOR]

For a finite Coxeter group W, Josuat-Verges derived a q-polynomial counting the maximal chains in the lattice of noncrossing partitions of W by weighting some of the covering relations, which we call bad edges, in these chains with a parameter q. We study the connection of these weighted chains with parking functions of type A (B, respectively) from the perspective of the q-polynomial. The q-polynomial turns out to be the generating function for parking functions (of either type) with respect to the number of cars that do not park in their preferred spaces. In either case, we present a bijective result that carries bad edges to unlucky cars while preserving their relative order. Using this, we give an interpretation of the \gamma -positivity of the q-polynomial in the case when W is the hyperoctahedral group. [ABSTRACT FROM AUTHOR]