Anusch Taraz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Anusch Taraz has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Julia Böttcher
Department of Mathematics The London School of Economics London UK
8 shared publications - Andreas Würfl
Zentrum Mathematik Technische Universität München Boltzmannstraße 3 D-85747 Garching bei München Germany
3 shared publications - Mathias Schacht
Universität Hamburg
3 shared publications Andreas Würfl
2 shared publications- Angelika Steger
Department of Computer Science ETH Zurich Switzerland
2 shared publications - Julia Böttcher
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil
2 shared publications
Latest Publications
- 1 August 2015
- Published by Elsevier in European Journal of Combinatorics
- Vol. 48, 165-176
Ramsey numbers for bipartite graphs with small bandwidth
- 1 August 2015
- Published by Elsevier in European Journal of Combinatorics
- Vol. 48, 165-176
Ramsey numbers for bipartite graphs with small bandwidth
- 8 August 2013
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (5) , 639-683
Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal
Let Δ ≥ 2 be a fixed integer. We show that the random graph ${\mathcal{G}_{n,p}}$ with $p\gg (\log n/n)^{1/\Delta}$ is robust with respect to the containment of almost spanning bipartite graphsHwith maximum degree Δ and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges from ${\mathcal{G}_{n,p}}$ in such a way that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all suchH.- 8 August 2013
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (5) , 639-683
Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal
Let Δ ≥ 2 be a fixed integer. We show that the random graph ${\mathcal{G}_{n,p}}$ with $p\gg (\log n/n)^{1/\Delta}$ is robust with respect to the containment of almost spanning bipartite graphsHwith maximum degree Δ and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges from ${\mathcal{G}_{n,p}}$ in such a way that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all suchH.- Open Access
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.
Open AccessAlmost 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.
- 14 May 2012
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 21 (5) , 661-682
Perfect Graphs of Fixed Density: Counting and Homogeneous Sets
For c ∈ (0,1) let n(c) denote the set of n-vertex perfect graphs with density c and let n(c) denote the set of n-vertex graphs without induced C5 and with density c.We show that with otherwise, where H is the binary entropy function.Further, we use this result to deduce that almost all graphs in n(c) have homogeneous sets of linear size. This answers a question raised by Loebl and co-workers.
- 14 May 2012
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 21 (5) , 661-682
Perfect Graphs of Fixed Density: Counting and Homogeneous Sets
For c ∈ (0,1) let n(c) denote the set of n-vertex perfect graphs with density c and let n(c) denote the set of n-vertex graphs without induced C5 and with density c.We show that with otherwise, where H is the binary entropy function.Further, we use this result to deduce that almost all graphs in n(c) have homogeneous sets of linear size. This answers a question raised by Loebl and co-workers.
- 1 December 2011
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 38, 181-186
Induced C5-free graphs of fixed density: counting and homogeneous sets
- 1 December 2011
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 38, 181-186
Induced C5-free graphs of fixed density: counting and homogeneous sets
- Open Access
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\'e [Almost all H-free graphs have the Erd\H{o}s-Hajnal property] in the case of forbidden induced C_5.
Open AccessPerfect 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\'e [Almost all H-free graphs have the Erd\H{o}s-Hajnal property] in the case of forbidden induced C_5.
- 1 January 2011
- Published by International Press of Boston in Journal of Combinatorics
- Vol. 2 (4) , 481-500
Primality of trees
- 1 January 2011
- Published by International Press of Boston in Journal of Combinatorics
- Vol. 2 (4) , 481-500
Primality of trees
- Open Access
Bandwidth, expansion, treewidth, separators, and universality for bounded degree graphs
We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an expanding subgraph of G. Our results imply that if one of these parameters is sublinear in the number of vertices of G then so are all the others. This implies for example that graphs of fixed genus have sublinear bandwidth or, more generally, a corresponding result for graphs with any fixed forbidden minor. As a consequence we establish a simple criterion for universality for such classes of graphs and show for example that for each gamma>0 every n-vertex graph with minimum degree ((3/4)+gamma)n contains a copy of every bounded-degree planar graph on n vertices if n is sufficiently large.
Open AccessBandwidth, expansion, treewidth, separators, and universality for bounded degree graphs
We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an expanding subgraph of G. Our results imply that if one of these parameters is sublinear in the number of vertices of G then so are all the others. This implies for example that graphs of fixed genus have sublinear bandwidth or, more generally, a corresponding result for graphs with any fixed forbidden minor. As a consequence we establish a simple criterion for universality for such classes of graphs and show for example that for each gamma>0 every n-vertex graph with minimum degree ((3/4)+gamma)n contains a copy of every bounded-degree planar graph on n vertices if n is sufficiently large.
- Open Access
Embedding into bipartite graphs
The conjecture of Bollob\'as and Koml\'os, recently proved by B\"ottcher, Schacht, and Taraz [Math. Ann. 343(1), 175--205, 2009], implies that for any $\gamma>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+\gamma)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+\gamma)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\'y 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.Open AccessEmbedding into bipartite graphs
The conjecture of Bollob\'as and Koml\'os, recently proved by B\"ottcher, Schacht, and Taraz [Math. Ann. 343(1), 175--205, 2009], implies that for any $\gamma>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+\gamma)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+\gamma)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\'y 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. - 20 August 2008
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 31, 91-96
Bandwidth, treewidth, separators, expansion, and universality
- 20 August 2008
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 31, 91-96
Bandwidth, treewidth, separators, expansion, and universality