Source author record

Anusch Taraz

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.LO math.PR

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The tree packing conjecture for trees of almost linear maximum degree

We prove that there is $c>0$ such that for all sufficiently large $n$ , if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$ , then $\{T_1,\dots,T_n\}$ packs into $K_n$ . Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.

preprint2020arXiv

The Bandwidth Theorem in Sparse Graphs

The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$ -vertex graph $G$ with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)n$ 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\gg \big(\tfrac{\log n}{n}\big)^{1/Δ}$ asymptotically almost surely each spanning subgraph $G$ of $G(n,p)$ with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)pn$ contains all $n$ -vertex $k$ -colourable graphs $H$ with maximum degree $Δ$ , bandwidth $o(n)$ , and at least $C p^{-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\gg \big(\tfrac{\log n}{n}\big)^{1/3}$ .

preprint2016arXiv

Ramsey numbers for bipartite graphs with small bandwidth

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.

preprint2014arXiv

Coloring d-Embeddable k-Uniform Hypergraphs

This paper extends the scenario of the Four Color Theorem in the following way. Let H(d,k) be the set of all k-uniform hypergraphs that can be (linearly) embedded into R^d. We investigate lower and upper bounds on the maximum (weak and strong) chromatic number of hypergraphs in H(d,k). For example, we can prove that for d>2 there are hypergraphs in H(2d-3,d) on n vertices whose weak chromatic number is Omega(log n/log log n), whereas the weak chromatic number for n-vertex hypergraphs in H(d,d) is bounded by O(n^((d-2)/(d-1))) for d>2.

preprint2014arXiv

Supporting document to the paper "Logical limit laws for minor-closed classes of graphs"

We provide a hand-checkable proof for Lemma 4.9 in the paper "Logical limit laws for minor-closed classes of graphs" by Heinig, Muller, Noy and Taraz.

preprint2013arXiv

Almost spanning subgraphs of random graphs after adversarial edge removal

Let Delta>1 be a fixed integer. We show that the random graph G(n,p) with p>>(log n/n)^{1/Delta} is robust with respect to the containment of almost spanning bipartite graphs H with maximum degree Delta and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges in G(n,p) such that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all such H.

preprint2013arXiv

An Extension of the Blow-up Lemma to arrangeable graphs

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 generalisations 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 neighbours to the right of any vertex v have at most a neighbours to the left of v in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a K_s-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most sqrt(n)/log(n) can be embedded into corresponding systems of super-regular 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 sqrt(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(2),269-282, 1996]. 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.

preprint2013arXiv

Spanning embeddings of arrangeable graphs with sublinear bandwidth

The Bandwidth Theorem of Böttcher, Schacht and Taraz [Mathematische Annalen 343 (1), 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)<sqrt(n)/log(n), where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least (3/4+γ)n contain almost all planar graphs on n vertices as subgraphs. Using techniques developed by Allen, Brightwell and Skokan [Combinatorica, to appear] 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.

preprint2011arXiv

Perfect graphs of fixed density: counting and homogenous sets

For c in [0,1] let P_n(c) denote the set of n-vertex perfect graphs with density c and C_n(c) the set of n-vertex graphs without induced C_5 and with density c. We show that log|P_n(c)|/binom{n}{2}=log|C_n(c)|/binom{n}{2}=h(c)+o(1) with h(c)=1/2 if 1/4<c<3/4 and h(c)=H(|2c-1|)/2 otherwise, where H is the binary entropy function. Further, we use this result to deduce that almost all graphs in C_n(c) have homogenous sets of linear size. This answers a question raised by Loebl, Reed, Scott, Thomason, and Thomassé [Almost all H-free graphs have the Erdős-Hajnal property] in the case of forbidden induced C_5.

preprint2009arXiv

Embedding into bipartite graphs

The conjecture of Bollobás and Komlós, recently proved by Böttcher, Schacht, and Taraz [Math. Ann. 343(1), 175--205, 2009], implies that for any $γ>0$ , every balanced bipartite graph on $2n$ vertices with bounded degree and sublinear bandwidth appears as a subgraph of any $2n$ -vertex graph $G$ with minimum degree $(1+γ)n$ , provided that $n$ is sufficiently large. We show that this threshold can be cut in half to an essentially best-possible minimum degree of $(\frac12+γ)n$ when we have the additional structural information of the host graph $G$ being balanced bipartite. This complements results of Zhao [to appear in SIAM J. Discrete Math.], as well as Hladký and Schacht [to appear in SIAM J. Discrete Math.], who determined a corresponding minimum degree threshold for $K_{r,s}$ -factors, with $r$ and $s$ fixed. Moreover, it implies that the set of Hamilton cycles of $G$ is a generating system for its cycle space.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Anusch Taraz

Research overview

Is this your work?

10 publications

The tree packing conjecture for trees of almost linear maximum degree

The Bandwidth Theorem in Sparse Graphs

Ramsey numbers for bipartite graphs with small bandwidth

Coloring d-Embeddable k-Uniform Hypergraphs

Supporting document to the paper "Logical limit laws for minor-closed classes of graphs"

Almost spanning subgraphs of random graphs after adversarial edge removal

An Extension of the Blow-up Lemma to arrangeable graphs

Spanning embeddings of arrangeable graphs with sublinear bandwidth

Perfect graphs of fixed density: counting and homogenous sets

Embedding into bipartite graphs

See the researcher in context

Building this map preview