查看更多>>摘要：We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph F, denote by mader ((x)over-right-arrow)(F) the smallest integer k such that every k-dichromatic digraph contains a subdivision of F. As our first main result, we prove that if F is an orientation of a cycle then mader, ((x)over-right-arrow)(F) = v(F). This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomasse. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. Our second main result is that mader (x)over-right-arrow (F) = 4 for every tournament F of order 4. This is an extension of the classical result by Dirac that 4-chromatic graphs contain a K-4-subdivision to directed graphs. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：We consider the problem of constructing a cyclic listing of all bitstrings of length 2n + 1 with Hamming weights in the interval [n + 1 - $, n + $], where 1 < $ < n + 1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (the case $ = 1). We provide a solution for the case $ = 2, and we solve a relaxed version of the problem for general values of $, by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube. The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets. We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Tutte's 3-flow conjecture states that every 4-edge-connected graph admits a nowhere-zero 3-flow. The planar case of Tutte's 3-flow conjecture is the classical Grotzsch's Theorem (1959). Steinberg and Younger (1989) further verified Tutte's 3-flow conjecture for projective planar graphs. In this paper we confirm Tutte's 3-flow conjecture for all toroidal graphs. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：A signed bipartite (simple) graph (G, sigma) is said to be C_(4)-critical if it admits no homomorphism to C_(4) (a negative 4 cycle) but each of its proper subgraphs does. To motivate the study of C_(4)-critical signed graphs, we show that the notion of 4-coloring of graphs and signed graphs is captured, through simple graph operations, by the notion of homomorphism to C_(4). In particular, the 4-color theorem is equivalent to: Given a planar graph G, the signed bipartite graph obtained from G by replacing each edge with a negative path of length 2 maps to C_(4). We prove that, except for one particular signed bipartite graph on 7 vertices and 9 edges, any C-4-critical signed graph on n vertices must have at least inverted right perpendicular 4n inverted left perpendicular edges. Moreover, we show that for each value of n >= 9 there exists a C_(4)-critical signed graph on n vertices with either inverted right perpendicular 4n inverted left perpendicular 1 or inverted right perpendicular 4n inverted left perpendicular + 1 many edges. As an application, we conclude that all signed bipartite planar graphs of negative girth at least 8 map to C_(4). Furthermore, we show that there exists an example of a signed bipartite planar graph of girth 6 which does not map to C_(4), showing 8 is the best possible and disproving a conjecture of Naserasr, Rollova and Sopena. (C) 2021 Published by Elsevier Inc.
查看更多>>摘要：For any even integer k > 6, integer d such that k/2 < d < k-1, and sufficiently large n is an element of (k/2)N, we find a tight minimum ddegree condition that guarantees the existence of a Hamilton (k/2)-cycle in every k-uniform hypergraph on n vertices. When n is an element of kN, the degree condition coincides with the one for the existence of perfect matchings provided by Rodl, Rucinski and Szemeredi (for d = k - 1) and Treglown and Zhao (for d > k/2), and thus our result strengthens theirs in this case. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：In the theory of classical matroids, there are several known equivalent axiomatic systems that define a matroid, which are described as matroid cryptomorphisms. A q-matroid is a q-analogue of a matroid where subspaces play the role of the subsets in the classical theory. In this article we establish cryptomorphisms of q-matroids. In doing so we highlight the difference between classical theory and its q-analogue. We introduce a comprehensive set of q-matroid axiom systems and show cryptomorphisms between them and existing axiom systems of a q-matroid. These axioms are described as the rank, closure, basis, independence, dependence, circuit, hyperplane, flat, open space, spanning space, non-spanning space, and bi-colouring axioms. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Let H-r(n, p) denote the maximum number of Hamiltonian cycles in an n-vertex r-graph with density p is an element of (0, 1). The expected number of Hamiltonian cycles in the random r-graph model G(r)(n, p) is E (n, p) = p(n)(n - 1)!/2and in the random graph model G(r)(n, m) with m = p(n r) it is, in fact, slightly smaller than E(n, p). For graphs, H-2(n, p) is proved to be only larger than E(n, p) by a polynomial factor and it is an open problem whether a quasi-random graph with density pcan be larger than E(n, p) by a polynomial factor. For hypergraphs (i.e. r >= 3) the situation is drastically different. For all r >= 3 it is proved that H-r(n, p) is larger than E(n, p) by an exponentialfactor and, moreover, there are quasi-random r-graphs with density pwhose number of Hamiltonian cycles is larger than E(n, p) by an exponential factor. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Let M be a 3-connected matroid, and let N be a 3-connected minor of M. A pair {x1, x2} C E(M) is N-detachable if one of the matroids M/x1/x2 or M\x1\x2 is 3-connected and has an N-minor. This is the third and final paper in a series where we prove that if |E(M)| - |E(N)| > 10, then either M has an N-detachable pair after possibly performing a single Delta-Y or Y-Delta exchange, or M is essentially N with a spike attached. Moreover, we describe the additional structures that arise if we require only that |E(M)| - |E(N)| > 5. (c) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier