Search

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]

While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for noninteger weights is that by Poljak and Turzik [Discrete Math., 58 (1986), pp. 99--104]. In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, the probabilistic method, Vizing's chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth, and triangle-free weighted graphs. We pose conjectures and open questions. [ABSTRACT FROM AUTHOR]

In this paper, we investigate representations of links that are either centrally symmetric in R3 or antipodally symmetric in S3. By using the notions of antipodally self-dual and antipodally symmetric maps, introduced and studied by the authors in [L. Montejano, J. L. Ramírez Alfonsín, and I. Rasskin, SIAM J. Discrete Math., 36 (2022), pp. 1551-1566], we are able to present sufficient combinatorial conditions for a link L to admit such representations. The latter naturally provide sufficient conditions for L to be amphichiral. We also introduce another (closely related) method yielding again sufficient conditions for L to be amphichiral. We finally prove that a link L, associated to a map G, is amphichiral if the self-dual pairing of G is not one of 6 specific cases among the classification of the 24 self-dual pairing Cor(G)⊳Aut(G). [ABSTRACT FROM AUTHOR]

Let r \geq k \geq 2 and K(k) r,n denote the complete n-balanced r-partite k-uniform hypergraph, whose vertex set consists of r parts, each has n vertices, and whose edge set contains all the k-element subsets with no two vertices from one part. A decomposition of K(k) r,n is a partition of E(K(k) r,n). A perfect matching (resp., Hamilton tight cycle) decomposition of K(k) r,n is a decomposition of K(k) r,n into perfect matchings (resp., Hamilton tight cycles). In this paper, we prove that if k | n (resp., 2 - k and k | n), then K(k) k+1,n (resp., K(k) k+2,n) has a perfect matching decomposition. We also prove that for any integer k \geq 2, K(k) k+1,n has a Hamilton tight cycle decomposition. In all cases, we use constructive methods involving number theory. In fact, we confirm two conjectures proposed by Zhang, Lu, and Liu [Appl. Math. Comput., 386 (2020), 125492]. [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

Let B(k) n be the book graph which consists of n copies of Kk+1 all sharing a common Kk, and let Cm be a cycle of length m. In this paper, we first determine the exact value of r(B(2) n,Cm) for 8 9n + 112 leq m leq lceil 3n 2 rceil + 1 and n geq 1000. This answers a question of Faudree, Rousseau, and Sheehan [Ars Combin., 31 (1991), pp. 239--248] in a stronger form when m and n are large. Building upon this exact result, we are able to determine the asymptotic value of r(B(k) n,Cn) for each k geq 3. Namely, we prove that for each k geq 3, r(B(k) n ,Cn) = (k + 1 + ok(1))n. This extends a result due to Rousseau and Sheehan [J. London Math. Soc., 18 (1978), pp. 392--396]. [ABSTRACT FROM AUTHOR]

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687{694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this conjecture. Further, we classify strong tournaments and strong bipartite tournaments of minimum out-degree 3 without two vertex disjoint directed cycles of different lengths. [ABSTRACT FROM AUTHOR]

A graph is said to be open-neighborhood conflict-free k-colorable if there exists an assignment of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among the neighbors of v. The open-neighborhood conflict-free chromatic number χO(G) is the smallest k for which G is open-neighborhood conflict-free k-colorable. Z. Abel et al., [SIAM J. Discrete Math. 32 (2018), pp. 2675--2702] showed that χ O(G) ≤ 8 for every planar graph G and posed two open problems to ask whether χO(G) \leq 4 for every planar graph G and whether χO(G) ≤ 3 for every outerplanar graph G. We present in this paper positive answers for the above two open problems by establishing a stronger result which states that, for every integer k ≥ 2, every minor-k-colorable graph is open-neighborhood conflict-free k-colorable, where a graph G is said to be minor-k-colorable if every minor of G is k-colorable. [ABSTRACT FROM AUTHOR]

A classic theorem of Erdös and Pósa [Canad. J. Math., 17 (1965), pp. 347--352] states that every graph has either k vertex-disjoint cycles or a set of O(k log k) vertices meeting all its cycles. While the standard proof revolves around finding a large 'frame" in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus [Random Structures Algorithms, 22 (2003), pp. 213--225] and Diestel and Rempel [Combinatorica, 25 (2005), pp. 111--116]. In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdös-Pósa theorem. As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos [Combinatorica, 39 (2019), pp. 1--36] that cycles of length at least l have the so-called edge-Erdös-Pósa property. More precisely, we show that every graph G contains either k edge-disjoint cycles of length at least l or an edge set F of size O(kl . log(kl)) such that G-F has no cycle of length at least l, For fixed l, this improves on the previously best known bound of O(k2 log k + kl). [ABSTRACT FROM AUTHOR]

This paper examines bounds on upper tails for cycle counts in Gn,p. For a fixed graph H define ξH =ξn,p H to be the number of copies of H in Gn,p. It is a much studied and surprisingly difficult problem to understand the upper tail of the distribution of ξH, for example, to estimate P(ξH > 2EξH). The best known result for general H and p is due to Janson, Oleszkiewicz, and Ruciński [Israel J. Math., 142 (2004), pp. 61--92], who proved that exp[ OH,η (MH(n, p) ln(1/p))] < P(ξH > (1 + η )EξH) < exp[-Ω H,η (MH(n, p))]. Thus they determined the upper tail up to a factor of ln(1/p) in the exponent. There has since been substantial work to improve these bounds for particular H and p. We close the ln(1/p) gap for cycles, up to a constant in the exponent. Here the lower bound stated above is accurate for l-cycles when p > ln¹/(l-2)n/n. [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a hypergraph H is called a Berge-G if there is a bijection f : E(G) → E(H) such that e ⊆ f(e) for all e ∈ E(G). The family of Berge-G hypergraphs is denoted by B(G). The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-G is denoted by exr(n, B (G)). Gyárfás [SIAM J. Discrete Math., 33 (2019), pp. 383-- 392] showed that for n ≥ 6, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. However, we found an error in the proof of the result when n ≥ 7. A recent result due to Gerbner, Methuku, and Palmer [European J. Combin., 86 (2020), 103082] implies that for n ≥ 9, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. In this paper we prove the remaining cases n = 7 and n = 8 for the completeness of the conclusion. [ABSTRACT FROM AUTHOR]

A cut varepsilon-sparsifier of a weighted graph G is a reweighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of varepsilon. Since their introduction by Benczur and Karger [Approximating s-t minimum cuts in O~ (n2) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC96), 1996, pp. 47-55], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIAM J. Discrete Math., 31 (2017), pp. 1263--1276] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. [ABSTRACT FROM AUTHOR]

Given a graph H, the Tur'an number ex(n,H) is the largest number of edges in an Hfree graph on n vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee [More on the Extremal Number of Subdivisions, arXiv:1903.10631v1, 2019] on the Tur'an numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdos and Simonovits [Combinatorica, 1 (1981), pp. 25-42]. Let s, t, k = 2 be integers. Let Kk s,t denote the graph obtained from the complete bipartite graph Ks,t by replacing each edge uv in it with a path of length k between u and v such that the st replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon [J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1747-1757] that ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Conlon, Janzer, and Lee recently conjectured that for any integers s, t, k = 2, ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Among many other things, they settled the k = 2 case of their conjecture. As the main result of this paper, we prove their conjecture for k = 3, 4. Our main results also yield infinitely many new so-called Tur'an exponents: rationals r ? (1, 2) for which there exists a bipartite graph H with ex(n,H) = T(nr), adding to the lists recently obtained by Jiang, Ma, and Yepremyan [On Tur'an Exponents of Bipartite Graphs, arXiv:1806.02838, 2018], by Kang, Kim, and Liu [On the Rational Tur'an Exponent Conjecture, arXiv:1811.06916, 2018], and by Conlon, Janzer, and Lee. Our method builds on an extension of the Conlon-Janzer-Lee method. We also note that the extended method also gives a weaker version of the Conlon-Janzer-Lee conjecture for all k = 2. [ABSTRACT FROM AUTHOR]

In this paper, we show that every (2P2, K4)-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [J. Combin. Theory Ser. B, 29 (1980), pp. 345-346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for (4P1,C4)-free graphs. Lozin and Malyshev [Discrete Appl. Math., 216 (2017), pp. 273-280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring (4P1,C4)-free graphs. [ABSTRACT FROM AUTHOR]

A family F of graphs on a fixed set of n vertices is called triangle-intersecting if for any G1,G2∈F, the intersection G1∩G2 contains a triangle. More generally, for a fixed graph H, a family F is H-intersecting if the intersection of any two graphs in F contains a sub-graph isomorphic to H. In [D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), pp. 841--885], Ellis, Filmus and Friedgut proved a 36-year old conjecture of Simonovits and Sós stating that the maximal size of a triangle-intersecting family is (1/8)2n(n-1)/2. Furthermore, they proved a p-biased generalization, stating that for any p≤1/2, we have μp(F)≤p3, where μp(F) is the probability that the random graph G(n,p) belongs to F. In the same paper, Ellis et al. conjectured that the assertion of their biased theorem holds also for 1/21/2, an H-intersecting family F of graphs such that μp(F)≥1--n2/C, where C depends only on H and p, thus disproving both conjectures. [ABSTRACT FROM AUTHOR]

Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris, and Samotij [J. Amer. Math. Soc., 28 (2015), pp. 669--709], and independently Saxton and Thomason [Invent. Math., 201 (2015), pp. 925--992], developed very general container theorems for independent sets in hypergraphs, both of which have seen numerous applications to a wide range of problems. In this paper we use the container method to give relatively short and elementary proofs of a number of results concerning Ramsey (and Turán) properties of (hyper)graphs and the integers. In particular we do the following: (a) We generalize the random Ramsey theorem of Rödl and Ruciński [Combinatorics, Paul Erdős Is Eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Mathematical Society, Budapest, 1993, pp. 317--346; Random Structures Algorithms, 5 (1994), pp. 253--270; J. Amer. Math. Soc., 8 (1995), pp. 917--942] by providing a resilience analogue. Our result unifies and generalizes several fundamental results in the area including the random version of Turán's theorem due to Conlon and Gowers [Ann. of Math., 184 (2016), pp. 367--454] and Schacht [Ann. of Math., 184 (2016), pp. 331--363]. (b) The above result also resolves a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter [Random Structures Algorithms, 11 (1997), pp. 245--276]. (c) All of the above results in fact hold for uniform hypergraphs. (d) For a (hyper)graph H, we determine, up to an error term in the exponent, the number of n-vertex (hyper)graphs G that have the Ramsey property with respect to H (that is, whenever G is r-colored, there is a monochromatic copy of H in G). (e) We strengthen the random Rado theorem of Friedgut, Rödl, and Schacht [Random Structures Algorithms, 37 (2010), pp. 407--436] by proving a resilience version of the result. (f) For partition regular matrices A we determine, up to an error term in the exponent, the number of subsets of { 1, . . . , n} for which there exists an r-coloring which contains no monochromatic solutions to Ax = 0. Along the way a number of open problems are posed. [ABSTRACT FROM AUTHOR]

A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak and Tuza [SIAM J. Discrete Math., 7 (1994), pp. 307--313] and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82] bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid and has appeared in dozens of combinatorial constructions. In this paper, we show a similar type of result for X (G) as a function of the number of vertices n, the number of edges m, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds. [ABSTRACT FROM AUTHOR]

A recent pair of papers by Armstrong, Loehr, and Warrington [preprint, arXiv:1403.1845, 2014] and Armstrong, Rhoades, and Williams [Electron J. Combin., 20 (2013), 54] initiated the systematic study of rational Catalan combinatorics, which is a generalization of Fuß--Catalan combinatorics (which is in turn a generalization of classical Catalan combinatorics). The latter paper gave two possible models for a rational analogue of the associahedron, which attaches simplicial complexes to any pair of coprime positive integers a < b. These complexes coincide up to the Fuß-Catalan level of generality, but at the rational level of generality one may be a strict subcomplex of the other. Verifying Conjecture 4.7 of [Electron J. Combin. 20 (2013), 54], we prove that these complexes agree up to homotopy and, in fact, that one complex collapses onto the other. This reconciles the two competing models for rational associahedra. As a corollary, we get that the involution (a < b) ↔ (b - a < b) on pairs of coprime positive integers manifests itself topologically as Alexander duality of rational associahedra. This collapsing and Alexander duality are new features of rational Catalan combinatorics which are invisible at the Fuß--Catalan level of generality. [ABSTRACT FROM AUTHOR]

In earlier papers we have developed an algebraic theory of discrete tomography. In those papers the structure of the functions f : A → {0, 1} and f : A → Z having given line sums in certain directions have been analyzed. Here was a block in Zn with sides parallel to the axes. In the present paper we assume that there is noise in the measurements and (only) that A is an arbitrary or convex finite set in Zn. We derive generalizations of earlier results. Furthermore we apply a method of Beck and Fiala to obtain results of the following type: if the line sums in k directions of a function h : A → [0, 1] are known, then there exists a function f : A → {0, 1} such that its line sums differ by at most k from the corresponding line sums of h. [ABSTRACT FROM AUTHOR]

In this paper we consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer q. Given a family F of q-multigraphs, define ex(n, F) to be the maximum number of edges (counting multiplicities) that a q-multigraph on n vertices can have without containing a copy of any F ∈ F (not necessarily induced). It is well known that τ(F) = limn→∞ ex(n, F)/(2n) exists for every family F (finite or infinite). Let T = {τ(F): F is a family of q-multigraphs}. We say the number α, 0 ≤ α < q, is a jump for q if there exists a constant c = c(α, q) such that if α' ∈ F such that α' > α, then α' ≥ α+c. The Erdős-Stone theorem implies that for q = 1, every α ∈ [0, 1) is a jump. The problem of determining the set of jumps for q ≥ 2 appears to be much harder. In a sequence of papers by Erdős, Brown, and Simonovits and, separately, Sidorenko, the authors established that every α is a jump for q = 2, leaving the question of whether the same is true for q ≥ 3 unresolved. A later result of Rödl and Sidorenko [V. Rödl and A. Sidorenko, J. Combin. Theory Ser. A, 69 (1995), pp. 347-357] gave a negative answer establishing that for q ≥ 4 some values of a are not jumps. The problem of whether or not every α ∈ [0, 3) is a jump for q = 3 has remained open. We give a partial positive result in this paper proving that every α ∈ [0, 2) is a jump for all q ≥ 3. Additionally, we extend the results of Rödl and Sidorenko by showing, given any rational number r with 0 < r ≤ 1, that (q-r) is not a jump for any q sufficiently large. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions on F2n are functions achieving the lowest possible differential uniformity. All APN functions discovered until now are either power or quadratic ones, except for one sporadic multinomial nonquadratic example on F26 due to Edel and Pott. It is well known that certain binary codes with good properties can be obtained from APN functions, and determining their (Hamming) weight distribution is equivalent to determining the Fourier spectra of the corresponding functions. The Fourier spectra of all known infinite families of quadratic APN functions discovered through 2010 have been determined, and it was found that they are the same as the ones of the Gold APN functions, i.e., a 5-valued set when n is even and a 3-valued set when n is odd, while a sporadic example on F26 found by Dillon has a 7-valued Fourier spectrum. In 2011, two new generic constructions of APN functions were presented in [Y. Zhou and A. Pott, Adv. Math., 234 (2013), pp. 43-60] and [C. Carlet, Des. Codes Cryptogr., 59 (2011), pp. 89-109]. In this paper, we determine the Fourier spectra of the APN functions obtained from them and show that their Fourier spectra are again the same as those of the Gold APN functions. Moreover, since the APN functions in [C. Bracken, C. H. Tan, and Y. Tan, On a Class of Quadratic Polynomials with No Zeros and Its Applications to APN Functions, preprint, arXiv:1110.3177v1, 2011], which are demonstrated to exist when n ≡ 0 mod 4 and 3 ∤ n, are covered by the construction in [C. Carlet, Des. Codes Cryptogr., 59 (2011), pp. 89-109], a positive answer to the conjecture proposed in the former paper on determining their Fourier spectrum is given in this paper. [ABSTRACT FROM AUTHOR]

Using the correspondence between regular polytopes and string C-groups, in a recent paper [M. E. Fernandes, D. Leemans, and M. Mixer, J. Combin. Theory Ser. A, 119 (2012), pp. 42--56], we constructed an regular polytope of rank r, for each r ≥ 3, with automorphism group isomorphic to A2r+3 when r is odd, and A2r+1 when r is even. In this paper, the remaining cases are completed. It is shown that every group An, with n sufficiently large, acts on at least one regular polytope of rank [n-1/2] We conjecture that this is the highest possible rank for n ≥ 12. [ABSTRACT FROM AUTHOR]

The goal of this paper is to develop a theoretical framework in order to analyze cooperative games in which only certain coalitions are allowed to form. We will axiomatize the structure of such allowable coalitions using the theory of antimatroids, a notion developed for combinatorially abstract sets. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. We introduce a new combinatorial structure called augmenting system, which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. The main result of the paper is a direct formula of Shapley and Banzhaf values for games under augmenting systems restrictions. [ABSTRACT FROM AUTHOR]

Let gd(n) be the set of d-regular simple graphs with n vertices, and for G = (V, E) in gd(n) let f : → {1, 2, . . . , n} be a objective coloring of the vertices of G. Also let α denote an interference parameter in {0, 1,. . . ,n - 1}, and define the interference number of f with respect to G and α as the number of edges {u, v} in E for which min{/f(u) - f(v)\,n - f(u) - f(v)\} < α. We consider two interference number problems for feasible (n, α, d). The first is to specify a G E and an f for which the interference number is as small as possible. The second is to determine a G &epsiv; gd(n) whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all d ≥ 3 and obtains partial results for the second problem for d ≥ 3 that focus on interference-minimizing f's when G consists of disjoint copies of Kd+1. [ABSTRACT FROM AUTHOR]

Given a directed graph G and an arc weight function w : E(G) → R+, the maximum directed cut problem (max dicut) is that of finding a directed cut δ(X) with maximum total weight. In this paper we consider a version of max dicut--max dicut with given sizes of parts or max dicut with gsp--whose instance is that of max dicut plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0,δ, 1/2, 1 - δ, 1}, where δ is a constant that satisfies 0 < δ < 1/2 and is the same for all components. [ABSTRACT FROM AUTHOR]

The graph of linear extensions G(P) of a poset P has as vertices the linear extensions of P, and two vertices are adjacent if they differ only by an adjacent transposition. This graph has so far been investigated mainly with respect to Hamilton paths and intrinsic geodesic convexity. The work on the latter topic especially shows how the graph-theoretic properties of G(P) reflect the order-theoretic structure of P. The aim of this paper is to study the graph G(P) with respect to topics from classical graph theory, e.g., connectivity, cycle space, isometric embeddings, and to find order-theoretic interpretations of these notions. The main theorems in this paper are the equality of the connectivity of G(P) and the jump number of P, the existence of a certain generating system for the cycle space, and a relationship of P and its subposets obtained via an embedding of the graph of linear extensions. [ABSTRACT FROM AUTHOR]

This is a sequel to a previous paper entitled The Order Dimension of Convex Polytopes, by the same authors [SIAM I Discrete Math., 6 (1993), pp. 230-245]. In that paper, we considered the poset PM formed by taking the vertices, edges, and faces of a 3-connected planar map M, ordered by inclusion, and showed that the order dimension of PM is always equal to 4. In this paper, we show that if M is any planar map, then the order dimension of PM is still at most 4. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, "hardwired" and "softwired," and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available. [ABSTRACT FROM AUTHOR]

In 1986, Thomassen posed the following conjecture: every 4-connected line graph has a Hamiltonian cycle. As a possible approach to the conjecture, many researchers have considered statements that are equivalent or related to it. One of them is the conjecture by Bondy: there exists a constant c0 with 0 < c0 ≤ 1 such that every cyclically 4-edge-connected cubic graph H has a cycle of length at least c0ΙV (H)Ι. It is known that Thomassen's conjecture implies Bondy's conjecture, but nothing about the converse has been shown. In this paper, we show that Bondy's conjecture implies a slightly weaker version of Thomassen's conjecture: every 4-connected line graph with minimum degree at least 5 has a Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

A plane graph G is entirely κ-colorable if V (G) ∪ E(G) ∪ F(G) can be colored with κ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph G with maximum degree Δ ≥ 12 is entirely (Δ + 2)-colorable. In this paper, we improve this result by showing that every plane graph G with Δ ≥ 9 is entirely (Δ + 2)-colorable. [ABSTRACT FROM AUTHOR]

This note is an erratum for the paper On the Inequalities of Projected Volumes and the Constructible Region [SIAM J. Discrete Math., 33 (2019), pp. 694--711]. There is a mistake in the proof of Theorem 4 in Section 3. However, Theorem 4 is itself correct (a proof can be found in [Inequalities on Projected Volumes, arxiv.org/abs/1909.12858, 2019] by Leader, Randelovic, and Raty), and all the other results of the paper stand. [ABSTRACT FROM AUTHOR]

Let G =(V1, V2, E) be a balanced bipartite graph with 2n vertices. The bipartite binding number of G, denoted by B(G), is defined to be n if G = Kn,n and mini∈{1,2} min... |N(S)|/|S| otherwise. We call G bipancyclic if it contains a cycle of every even length m for 4 m 2n. The purpose of this paper is to show that if B(G) > 3/2 and n ≥ 139, then G is bipancyclic; the bound 3/2 is best possible in the sense that there exist infinitely many balanced bipartite graphs G that have B(G)=3/2 but are not Hamiltonian. [ABSTRACT FROM AUTHOR]

In this paper we show that, with 11 exceptions, any matching covered bipartite graph on n vertices, with minimum degree greater than two, has at least 2n - 4 perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124-169] on brace generation, we show that any brace on n vertices has at least (n-2)²/8 perfect matchings. A bi-wheel on n vertices has (n - 2)²/4 perfect matchings. We conjecture that there exists an integer such that every brace on n ≥ N vertices has at least (n-2)²/4 perfect matchings. [ABSTRACT FROM AUTHOR]

An old problem raised independently by Jacobson and Schönheim seeks to determine the maximum for which every graph with edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. In this paper we determine this maximum up to a constant factor. We show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c(m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdös, Pach, and Pyber from 1987. [ABSTRACT FROM AUTHOR]

In this paper we employ Tutte's theory of bridges to derive a decomposition theorem for binary matroids arising from signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not based on κ-sums but rather on the operation of deletion of a cocircuit. Specifically, it is shown that certain minors resulting from the deletion of a cocircuit of a binary matroid will be graphic matroids, apart from exactly one that will be signed-graphic, if and only if the matroid is signed-graphic. [ABSTRACT FROM AUTHOR]

A graph G is called (r, s)-edge-choosable if for every assignment of sets of size r to the edges of G it is possible to choose for every edge an s-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph G is the infimum of all numbers r/s for which G is (r, s)-edge-choosable. Mohar [http://www.fmf.uni-lj.si/~mohar/(June 2003)] posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Math., 23 (2009), pp. 872-881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable-cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index 7/2. The original question of Mohar remains open, and we further pose several related problems. [ABSTRACT FROM AUTHOR]

A graph G of order n is said to be ∑' labeled if there exist a bijection f : V (G) → [n] and a constant c such that for all v ∈ V(G), ∑u∈N[v]f(u) = c. The uniqueness of the constant c has been an open question that was posed by Prof. Arumugam at the 2010 IWOGL Conference in Duluth. The question of the uniqueness of such a constant can be extended to arbitrary neighborhoods and to arbitrary sets of labels. For a set D ⊂ N, let ND(v) = {u ∈ V(G): d(u, v) ∈ D}, and let W be a multiset of real numbers. Graph G is said to be (D, W)-vertex magic if there exists a bijection g : V(G) → W such that for all v ∈ V(G), ∑u∈ND(v)g(u) is a constant, called the (D, W)-vertex magic constant. In this paper we prove that, even for these more general conditions, a (D, W)-vertex magic constant will be unique. Moreover, the constant can be determined using a generalization of the fractional domination number of the graph. [ABSTRACT FROM AUTHOR]

It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992-1999], proved an upper bound of ckw² on the number of chains used by First-Fit for some constant c, while Joret and Milans [Order, 28 (2011), pp. 455-464] gave one of ck²w. In this paper we prove an upper bound of the form ckw. This is most possible up to the value of c. [ABSTRACT FROM AUTHOR]

In this paper, we construct new families of graphs whose automorphism groups are transitive on 3-paths. These graphs are constructed from certain Lie algebras related to generalized Kac-Moody algebras of rank two. We will show that one particular subfamily gives new lower bounds on the number of edges in extremal graphs with no cycles of length fourteen. [ABSTRACT FROM AUTHOR]

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game. [ABSTRACT FROM AUTHOR]

Let Δ (G) be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number X(G) = Δ (G) + 1 are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number Xf(G) is at least Δ (G). These graphs are complete graphs, odd cycles, C²8 C5 ⊠ K2, and graphs whose clique number ω(G) equals the maximum degree Δ (G). Among the two sporadic graphs, the graph C²8 is the square graph of cycle C8, while the other graph C5 ⊠ K2 is the strong product of C5 and K2. In fact, we prove a stronger result: If a connected graph G with δ (G) ≥ 4 is not one of the graphs listed above, then we have Xf(G)≤ Δ(G) -- 2/67. [ABSTRACT FROM AUTHOR]

Thomassen [Combinatorica, 3 (1983), pp. 393--396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a graph. A set S⊆V is independent if no two vertices from are adjacent, while core(G) is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149-161]. The independence number α(G)is the cardinality of a largest independent set, and µ(G) is the size of a maximum matching of G. The neighborhood of A⊆V is N(A)= {v ∈ V : N(v)∩=0. The number dc(G)=max{|X|-|N(X)| : X ⊆ V} is called the critical di?erence of G, and is critical if |A|-|N(A)| = dc(G) [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431-438]. We define ker(G) as the intersection of all critical sets. In this paper we prove that if dc(G) ≥ 1, then ker(G) ⊆ core(G) and |ker(G)| >dc(G) ≥ α(G)-µ(G). [ABSTRACT FROM AUTHOR]

Given k labelings of a finite d-dimensional cubical grid, define the combined distance between two labels to be the sum of the l1-distance between the two labels in each labeling. We want to construct k labelings which maximize the minimum combined distance between any two labels. When d = 1, this can be interpreted as placing n nonattacking rooks in a k-dimensional chessboard of size n in such a way to maximize the minimum l1-distance between any two rooks. Rook placements are also known as Latin hypercube designs in the literature. In this paper, we revisit this problem with a more geometric approach. Instead of providing explicit but complicated formulas, we construct rook placements in a k-dimensional chessboard of size n as certain lattice-like structures for certain well-chosen values of n. Then, we extend these constructions to any values of n using geometric arguments. With this method, we present a clean and geometric description of the known optimal rook placements in the two-dimensional square grid. Furthermore, we provide asymptotically optimal constructions of k labelings of d-dimensional cubical grids which maximize the minimum combined distance. Finally, we discuss the extension of this problem to labelings of an arbitrary graph. We prove that deciding whether a graph has two labelings with combined distance at least 3 is at least as hard as graph isomorphism. [ABSTRACT FROM AUTHOR]

In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph G. Cops and a robber are allowed to move along the edges of G, and the goal of cops is to capture the robber. The cop number c(G) of G is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that O(√n) cops are enough for any connected G on n vertices. Improving several previous results, we prove that the cop number of an n-vertex graph is at most n2-(1+0(1))√log n.A similar result independently and slightly before us was also obtained by Lu and Peng. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

In multiflow maximization problems, there are several combinatorial duality relations, such as the Ford-Fulkerson max-flow min-cut theorem for single commodity flows, Hu's max-biflow min-cut theorem for two-commodity flows, the Lovász-Cherkassky duality theorem for free multiflows, and so on. In this paper, we provide a unified framework for such multiflow combinatorial dualities by using the notion of a folder complex, which is a certain 2-dimensional polyhedral complex introduced by Chepoi. We show that for a nonnegative weight μ on terminal set, the μ-weighted maximum multiflow problem admits a combinatorial duality relation if and only if μ is represented by distances between certain subsets in a folder complex, and we show that the corresponding combinatorial dual problem is a discrete location problem on the graph of the folder complex. This extends a result of Karzanov in the case of metric weights. [ABSTRACT FROM AUTHOR]

In the (k, λ)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and λ, and the goal is to find a minimum cost simple λ-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost λ-edge-connected spanning subgraph (which is a (|V(G)|, λ-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log² n)-approximation (even for 2-node-connectivity) and that the (k, λ)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle in equality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, λ)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity. [ABSTRACT FROM AUTHOR]

It has long been open whether all pairs of proper decimations of l-sequences based on primes are cyclically distinct. By determining the nontrivial maximal autocorrelation of l-sequences, this paper presents a partial proof of the distinctness problem. Since the proof idea is completely different from former ones, the set of decimations that are known to be cyclically distinct is further enlarged. On the basis of convincing experimental data, the proof seems to ensure that more than 79% of l-sequences based on different primes satisfy the fact that every pair of proper decimations is cyclically distinct. In particular, a complete proof is provided for l-sequences based on primes of the form 2 · r + 1, where r is an odd prime number. [ABSTRACT FROM AUTHOR]

For a real c = 1 and an integer n, let f(n, c) denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n, 1) vertices. The problem of estimating f(n, 1) was posed long ago by Erdős, Fajtlowicz, and Staton. In this paper we obtain the following upper and lower bounds for the asymptotic behavior of f(n, c): (i) For fixed c > 2.1, n1-O(1/c) ≤ f(n, c) ≤ O(cn/log n). (ii) For fixed c = 1+ε with e > 0 sufficiently small, f(n, c) ≥ nΩ(ε²/ln(1/ε)). (iii) O(ln n) ≤ f(n, 1) ≤ O(n1/2 ln3/4 n). An analogous problem for not necessarily induced subgraphs is briefly considered as well. [ABSTRACT FROM AUTHOR]