TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sun, 29 Jan 2023 17:05:46 GMT2023-01-29T17:05:46Z50181- The bandwidth theorem in sparse graphshttp://hdl.handle.net/11420/7750Title: The bandwidth theorem in sparse graphs
Authors: Allen, Peter; Böttcher, Julia; Ehrenmüller, Julia; Taraz, Anusch
Abstract: The bandwidth theorem [Mathematische Annalen, 343(1):175–205, 2009] states that any n-vertex graph G with minimum degree [Formula Presented] contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). We provide sparse analogues of this statement in random graphs as well as pseudorandom graphs. More precisely, we show that for p ≫[Formula Presented] asymptotically almost surely each spanning subgraph G of G(n, p) with minimum degree [Formula Presented] pn contains all n-vertex k-colourable graphs H with maximum degree ∆, bandwidth o(n), and at least Cp−2 vertices not contained in any triangle. A similar result is shown for sufficiently bijumbled graphs, which, to the best of our knowledge, is the first resilience result in pseudorandom graphs for a rich class of spanning subgraphs. Finally, we provide improved results for H with small degeneracy, which in particular imply a resilience result in G(n, p) with respect to the containment of spanning bounded degree trees for p ≫[Formula Presented].
Fri, 15 May 2020 00:00:00 GMThttp://hdl.handle.net/11420/77502020-05-15T00:00:00Z
- Approximating Minimum k-Section in Trees with Linear Diameterhttp://hdl.handle.net/11420/8687Title: Approximating Minimum k-Section in Trees with Linear Diameter
Authors: Fernandes, Cristina G.; Schmidt, Tina Janne; Taraz, Anusch
Abstract: Minimum k-Section denotes the NP-hard problem to partition the vertex set of a graph into k sets of size as equal as possible while minimizing the cut width, which is the number of edges between these sets. When k is an input parameter and n denotes the number of vertices, it is NP-hard to approximate the width of a minimum k-section within a factor of nc for any c<1, even when restricted to trees with constant diameter. Here, we show that every tree T allows a k-section of width at most (k-1)(2+16n/diam(T))δ(T). This implies a polynomial time constant factor approximation for the Minimum k-Section Problem when restricted to trees with linear diameter and constant maximum degree.
Tue, 01 Dec 2015 00:00:00 GMThttp://hdl.handle.net/11420/86872015-12-01T00:00:00Z
- Artificial intelligence and operations research in maritime logisticshttp://hdl.handle.net/11420/8045Title: Artificial intelligence and operations research in maritime logistics
Authors: Dornemann, Jorin; Rückert, Nicolas; Fischer, Kathrin; Taraz, Anusch
Abstract: Purpose: The application of artificial intelligence (AI) has the potential to lead to huge progress in combination with Operations Research methods. In our study, we explore current approaches for the usage of AI methods in solving optimization prob-lems. The aim is to give an overview of recent advances and to investigate how they are adapted to maritime logistics. Methodology: A structured literature review is conducted and presented. The iden-tified papers and contributions are categorized and classified, and the content and results of some especially relevant contributions are summarized. Moreover, an eval-uation, identifying existing research gaps and giving an outlook on future research directions, is given. Findings: Besides an inflationary use of AI keywords in the area of optimization, there has been growing interest in using machine learning to automatically learn heuristics for optimization problems. Our research shows that those approaches mostly have not yet been adapted to maritime logistics problems. The gaps identi-fied provide the basis for developing learning models for maritime logistics in future research. Originality: Using methods of machine learning in the area of operations research is a promising and active research field with a wide range of applications. To review these recent advances from a maritime logistics' point of view is a novel approach which could lead to advantages in developing solutions for large-scale optimization problems in maritime logistics in future research and practice.
Wed, 23 Sep 2020 00:00:00 GMThttp://hdl.handle.net/11420/80452020-09-23T00:00:00Z
- Coloring d-embeddable k-uniform hypergraphshttp://hdl.handle.net/11420/9901Title: Coloring d-embeddable k-uniform hypergraphs
Authors: Heise, Carl Georg; Panagiotou, Konstantinos; Pikhurko, Oleg; Taraz, Anusch
Abstract: This paper extends the scenario of the Four Color Theorem in the following way. Let Hd,k be the set of all k-uniform hypergraphs that can be (linearly) embedded into Rd. We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in Hd,k. For example, we can prove that for (Formula presented.) there are hypergraphs in H2d-3,d on n vertices whose chromatic number is Ω(log n/log log n), whereas the chromatic number for n-vertex hypergraphs in Hd,d is bounded by (Formula presented.).
Fri, 17 Oct 2014 00:00:00 GMThttp://hdl.handle.net/11420/99012014-10-17T00:00:00Z
- On minimum bisection and related cut problems in trees and tree-like graphshttp://hdl.handle.net/11420/2827Title: On minimum bisection and related cut problems in trees and tree-like graphs
Authors: Fernandes, Cristina G.; Schmidt, Tina Janne; Taraz, Anusch
Abstract: Minimum bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. It is intuitively clear that graphs with a somewhat linear structure are easy to bisect, and therefore our aim is to relate the minimum bisection width of a bounded-degree graph G to a parameter that measures the similarity between G and a path. First, for trees, we use the diameter and show that the minimum bisection width of every tree T on n vertices satisfies MinBis (T)≤8nΔ(T)/ diam (T). Second, we generalize this to arbitrary graphs with a given tree decomposition (T,X) and give an upper bound on the minimum bisection width that depends on how close (T,X) is to a path decomposition. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
Mon, 01 Oct 2018 00:00:00 GMThttp://hdl.handle.net/11420/28272018-10-01T00:00:00Z
- Logical limit laws for minor-closed classes of graphshttp://hdl.handle.net/11420/2945Title: Logical limit laws for minor-closed classes of graphs
Authors: Heinig, Peter; Müller, Tobias; Noy, Marc; Taraz, Anusch
Abstract: Let G be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all connected graphs in G on n vertices, and the convergence law in MSO holds if we draw uniformly at random from all graphs in G on n vertices. We also prove analogues of these results for the class of graphs embeddable on a fixed surface, provided we restrict attention to first order logic (FO). Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface S. We also prove that the closure of the set of limiting probabilities is always the finite union of at least two disjoint intervals, and that it is the same for FO and MSO. For the classes of forests and planar graphs we are able to determine the closure of the set of limiting probabilities precisely. For planar graphs it consists of exactly 108 intervals, each of the same length ≈5.39⋅10 −6 . Finally, we analyse examples of non-addable classes where the behaviour is quite different. For instance, the zero-one law does not hold for the random caterpillar on n vertices, even in FO.
Tue, 01 May 2018 00:00:00 GMThttp://hdl.handle.net/11420/29452018-05-01T00:00:00Z
- Local resilience of spanning subgraphs in sparse random graphshttp://hdl.handle.net/11420/10812Title: Local resilience of spanning subgraphs in sparse random graphs
Authors: Allen, Peter; Böttcher, Julia; Ehrenmüller, Julia; Taraz, Anusch
Abstract: For each real γ>0 and integers δ≥2 and k≥1, we prove that there exist constants β>0 and C>0 such that for all p≥C(logn/n)1/δ the random graph G(n, p) asymptotically almost surely contains - even after an adversary deletes an arbitrary (1/k-γ)-fraction of the edges at every vertex - a copy of every n-vertex graph with maximum degree at most δ, bandwidth at most βn and at least Cmaxp-2, p-1logn vertices not in triangles.
Thu, 12 Nov 2015 00:00:00 GMThttp://hdl.handle.net/11420/108122015-11-12T00:00:00Z
- Counting results for sparse pseudorandom hypergraphs IIhttp://hdl.handle.net/11420/3829Title: Counting results for sparse pseudorandom hypergraphs II
Authors: Kohayakawa, Yoshiharu; Mota, Guilherme Oliveira; Schacht, Mathias; Taraz, Anusch
Abstract: We present a variant of a universality result of Rödl (1986) for sparse, 3-uniform hypergraphs contained in strongly jumbled hypergraphs. One of the ingredients of our proof is a counting lemma for fixed hypergraphs in sparse “pseudorandom” hypergraphs, which is proved in the companion paper (Counting results for sparse pseudorandom hypergraphs I).
Sun, 01 Oct 2017 00:00:00 GMThttp://hdl.handle.net/11420/38292017-10-01T00:00:00Z
- Counting results for sparse pseudorandom hypergraphs Ihttp://hdl.handle.net/11420/3830Title: Counting results for sparse pseudorandom hypergraphs I
Authors: Kohayakawa, Yoshiharu; Mota, Guilherme Oliveira; Schacht, Mathias; Taraz, Anusch
Abstract: We establish a so-called counting lemma that allows embeddings of certain linear uniform hypergraphs into sparse pseudorandom hypergraphs, generalizing a result for graphs (Kohayakawa et al., 2004). Applications of our result are presented in the companion paper (Counting results for sparse pseudorandom hypergraphs II).
Sun, 01 Oct 2017 00:00:00 GMThttp://hdl.handle.net/11420/38302017-10-01T00:00:00Z
- Ramsey numbers for bipartite graphs with small bandwidthhttp://hdl.handle.net/11420/3474Title: Ramsey numbers for bipartite graphs with small bandwidth
Authors: Mota, Guilherme Oliveira; Sárközy, G. N.; Schacht, Mathias; Taraz, Anusch
Abstract: We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.
Sat, 01 Aug 2015 00:00:00 GMThttp://hdl.handle.net/11420/34742015-08-01T00:00:00Z
- Spanning embeddings of arrangeable graphs with sublinear bandwidthhttp://hdl.handle.net/11420/5959Title: Spanning embeddings of arrangeable graphs with sublinear bandwidth
Authors: Böttcher, Julia; Taraz, Anusch; Würfl, Andreas
Abstract: The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175-205] gives minimum degree conditions for the containment of spanning graphs H with small bandwidth and bounded maximum degree. We generalise this result to a-arrangeable graphs H with Δ(H)≤n/logn, where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least (34+γ)n contain almost all planar graphs on n vertices as subgraphs. Using techniques developed by Allen, et al. [Combinatorica 33 (2013), 125-160] we can also apply our methods to show that almost all planar graphs H have Ramsey number at most 12|H|. We obtain corresponding results for graphs embeddable on different orientable surfaces.
Tue, 01 Mar 2016 00:00:00 GMThttp://hdl.handle.net/11420/59592016-03-01T00:00:00Z
- An approximate version of the tree packing conjecturehttp://hdl.handle.net/11420/5974Title: An approximate version of the tree packing conjecture
Authors: Böttcher, Julia; Hladký, Jan; Piguet, Diana; Taraz, Anusch
Abstract: We prove that for any pair of constants ɛ > 0 and Δ and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most Δ, and with at most (n2) edges in total packs into (Formula presented.). This implies asymptotic versions of the Tree Packing Conjecture of Gyárfás from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.
Mon, 01 Feb 2016 00:00:00 GMThttp://hdl.handle.net/11420/59742016-02-01T00:00:00Z
- A counting lemma for sparse pseudorandom hypergraphshttp://hdl.handle.net/11420/6365Title: A counting lemma for sparse pseudorandom hypergraphs
Authors: Kohayakawa, Yoshiharu; Mota, Guilherme Oliveira; Schacht, Mathias; Taraz, Anusch
Abstract: We establish so-called counting lemmas that allow embeddings of certain hyper-graphs into sparse "pseudorandom" hypergraphs. As an application, we present a variant of a universality result of Rödl for sparse, 3-uniform hypergraphs contained in strongly pseudorandom hypergraphs.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11420/63652015-01-01T00:00:00Z
- An extension of the blow-up lemma to arrangeable graphshttp://hdl.handle.net/11420/10839Title: An extension of the blow-up lemma to arrangeable graphs
Authors: Böttcher, Julia; Kohayakawa, Yoshiharu; Taraz, Anusch; Würfl, Andreas
Abstract: The blow-up lemma established by Komlós, Sárközy, and Szemerédi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalizations of this result concerning the embedding of a-arrangeable graphs, where a graph is called a-arrangeable if its vertices can be ordered in such a way that the neighbors to the right of any vertex v have at most a neighbors to the left of v in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a Ks-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most √ n/ log n can be embedded into corresponding systems of superregular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph G with minimum degree at least (r-1 r + γ)n contains an F-factor of every a-arrangeable r-chromatic graph F with at most ζn vertices and maximum degree at most √ n/ log n, as long as ζ is sufficiently small compared to γ/(ar). This extends a result of Alon and Yuster [J. Combin. Theory Ser. B, 66 (1996), pp. 269-282]. Moreover, we show that for constant p the random graph G(n, p) is universal for the class of a-arrangeable n-vertex graphs H of maximum degree at most ζn/ log n, as long as ζ is sufficiently small compared to p/a. © 2015 Society for Industrial and Applied Mathematics.
Thu, 04 Jun 2015 00:00:00 GMThttp://hdl.handle.net/11420/108392015-06-04T00:00:00Z
- On the size-Ramsey number of grid graphshttp://hdl.handle.net/11420/11074Title: On the size-Ramsey number of grid graphs
Authors: Clemens, Dennis; Miralaei, Meysam; Reding, Damian; Schacht, Mathias; Taraz, Anusch
Abstract: The size-Ramsey number of a graph F is the smallest number of edges in a graph G with the Ramsey property for F, that is, with the property that any 2-colouring of the edges of G contains a monochromatic copy of F. We prove that the size-Ramsey number of the grid graph on n × n vertices is bounded from above by n 3+o(1).
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/110742021-01-01T00:00:00Z
- On minimum bisection and related partition problems in graphs with bounded tree widthhttp://hdl.handle.net/11420/11365Title: On minimum bisection and related partition problems in graphs with bounded tree width
Authors: Fernandes, Cristina G.; Schmidt, Tina Janne; Taraz, Anusch
Abstract: Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the number of edges between these two sets. We consider this problem in bounded degree graphs with a given tree decomposition (T, X) and prove an upper bound for their minimum bisection width in terms of the structure and width of (T, X). When (T, X) is provided as input, a bisection satisfying our bound can be computed in time proportional to the encoding length of (T, X). Furthermore, our result can be generalized to k-section, which is known to be APX-hard even when restricted to trees with bounded degree.
Thu, 12 Nov 2015 00:00:00 GMThttp://hdl.handle.net/11420/113652015-11-12T00:00:00Z
- A spanning bandwidth theorem in random graphshttp://hdl.handle.net/11420/11418Title: A spanning bandwidth theorem in random graphs
Authors: Allen, Peter; Böttcher, Julia; Ehrenmüller, Julia; Schnitzer, Jakob; Taraz, Anusch
Abstract: The bandwidth theorem of Böttcher, Schacht and Taraz states that any n-vertex graph G with minimum degree <![CDATA[ (k-1k+o(1))n ]]> contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). Recently, a subset of the authors proved a random graph analogue of this statement: for <![CDATA[ p≫ (nn)¹/Δ ]]> a.a.s. each spanning subgraph G of G(n,p) with minimum degree <![CDATA[ (k-1k+o(1))pn ]]> contains all n-vertex k-colourable graphs H with maximum degree <![CDATA[ Δ ]]>, bandwidth o(n), and at least <![CDATA[ C p⁻² ]]> vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper, we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in G contain many copies of <![CDATA[ KΔ ]]> then we can drop the restriction on H that <![CDATA[ Cp⁻² ]]> vertices should not be in triangles.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/114182021-01-01T00:00:00Z
- Perfectly packing graphs with bounded degeneracy and many leaveshttp://hdl.handle.net/11420/14550Title: Perfectly packing graphs with bounded degeneracy and many leaves
Authors: Allen, Peter; Böttcher, Julia; Clemens, Dennis; Taraz, Anusch
Abstract: We prove that one can perfectly pack degenerate graphs into complete or dense n-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree(Formula Presented.)., and in addition Ω(n) of them have at most (1 − Ω(1))n vertices and Ω(n) leaves. This proves Ringel’s conjecture and the Gyárfás Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).
Sat, 01 Jan 2022 00:00:00 GMThttp://hdl.handle.net/11420/145502022-01-01T00:00:00Z