Institute of Theoretical Computer Science

output

20052022

most citedThe Uncertainty Principle in the Presence of Quantum Memory

850 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing math.COShow all

22 papers · 1 filter

math.CO2022

On approximating the rank of graph divisors

Kristóf Bérczi, Hung P. Hoang, Lilla Tóthmérész

Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theor…

math.CO2017

A new upper bound on the game chromatic index of graphs

Ralph Keusch

We study the two-player game where Maker and Breaker alternately color the edges of a given graph $G$ with $k$ colors such that adjacent edges never get the same color. Maker's goa…

math.CO2017★ 2 cited

Local resilience of an almost spanning $k$ -cycle in random graphs

Nemanja Škorić, Angelika Steger, Miloš Trujić

The famous Pósa-Seymour conjecture, confirmed in 1998 by Komlós, Sárközy, and Szemerédi, states that for any $k \geq 2$ , every graph on $n$ vertices with minimum degree $kn/(k + 1)…

math.CO2016★ 2 cited

Colorability Saturation Games

Ralph Keusch

We consider the following two-player game: Maxi and Mini start with the empty graph on $n$ vertices and take turns, always adding one additional edge to the graph such that the chr…

math.CO2015★ 2 cited

Almost-spanning universality in random graphs

David Conlon, Asaf Ferber, Rajko Nenadov +1

A graph $G$ is said to be $H (n, Δ)$ -universal if it contains every graph on $n$ vertices with maximum degree at most $Δ$ . It is known that for any $ε > 0$ and any…

math.CO2014

On the threshold for the Maker-Breaker $H$ -game

Rajko Nenadov, Angelika Steger, Miloš Stojaković

We study the Maker-Breaker $H$ -game played on the edge set of the random graph $G_{n, p}$ . In this game two players, Maker and Breaker, alternately claim unclaimed edges of $G_{n,p}…

math.CO2014★ 2 cited

Higher Dimensional Discrete Cheeger Inequalities

Anna Gundert, May Szedlák

For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of…

math.CO2013★ 3 cited

Universality of random graphs and rainbow embedding

Asaf Ferber, Rajko Nenadov, Ueli Peter

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of $G (n, p)$ . Let the \emph{maximum density} of a graph $H$ be the…

math.CO2013★ 1 cited

Generating random graphs in biased Maker-Breaker games

Asaf Ferber, Michael Krivelevich, Humberto Naves

We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to…

math.CO2013★ 2 cited

Lower bounds on geometric Ramsey functions

Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado +1

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $R^{d}$ . A $k$ -ary semialgebraic predicate $Φ (x_{1}, \dots, x_{k})$ on $\mathbb{R…

math.CO2012★ 1 cited

Counting and packing Hamilton cycles in dense graphs and oriented graphs

Asaf Ferber, Michael Krivelevich, Benny Sudakov

We present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We utilize this approach to prove several ex…

math.CO2012★ 25 cited

Erdos-Szekeres-type statements: Ramsey function and decidability in dimension 1

Boris Bukh, Jiri Matousek

A classical and widely used lemma of Erdos and Szekeres asserts that for every n there exists N such that every N-term sequence a of real numbers contains an n-term increasing subs…

math.CO2011★ 15 cited

Construction of 2-factors in the middle layer of the discrete cube

Torsten Mütze, Franziska Weber

Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length $2 n + 1$ that have exactly $n$ or $n + 1$ entries equal to 1, with an edge between any…

math.CO2011★ 3 cited

On globally sparse Ramsey graphs

Torsten Mütze, Ueli Peter

We say that a graph $G$ has the Ramsey property w.r.t.\ some graph $F$ and some integer $r \geq 2$ , or $G$ is $(F, r)$ -Ramsey for short, if any $r$ -coloring of the edges of $G$ conta…

math.CO2011★ 3 cited

Coloring random graphs online without creating monochromatic subgraphs

Torsten Mütze, Thomas Rast, Reto Spöhel

Consider the following random process: The vertices of a binomial random graph $G_{n, p}$ are revealed one by one, and at each step only the edges induced by the already revealed ve…

math.CO2011

On the path-avoidance vertex-coloring game

Torsten Mütze, Reto Spöhel

For any graph $F$ and any integer $r \geq 2$ , the \emph{online vertex-Ramsey density of $F$ and $r$ }, denoted $m^{*} (F, r)$ , is a parameter defined via a deterministic two-player Ramse…

math.CO2011★ 4 cited

On Gromov's Method of Selecting Heavily Covered Points

Jiří Matoušek, Uli Wagner

A result of Boros and Füredi ( $d = 2$ ) and of Bárány (arbitrary $d$ ) asserts that for every $d$ there exists $c_{d} > 0$ such that for every $n$ -point set $P \subset R^{d}$ , some point of…

math.CO2010★ 13 cited

Counting Unique-Sink Orientations

Jan Foniok, Bernd Gärtner, Lorenz Klaus +1

Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear compl…

math.CO2010★ 35 cited

Hitting time results for Maker-Breaker games

Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz +1

We study Maker-Breaker games played on the edge set of a random graph. Specifically, we consider the random graph process and analyze the first time in a typical random graph proce…

math.CO2009

Probabilistic one-player Ramsey games via deterministic two-player games

Michael Belfrage, Torsten Mütze, Reto Spöhel

Consider the following probabilistic one-player game: The board is a graph with $n$ vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at rand…

math.CO2008★ 44 cited

Lower bounds for weak epsilon-nets and stair-convexity

Boris Bukh, Jiří Matoušek, Gabriel Nivasch

A set N is called a "weak epsilon-net" (with respect to convex sets) for a finite set X in R^d if N intersects every convex set that contains at least epsilon*|X| points of X. For…

math.CO2005★ 19 cited

Two New Bounds on the Random-Edge Simplex Algorithm

Bernd Gärtner, Volker Kaibel

We prove that the Random-Edge simplex algorithm requires an expected number of at most 13n/sqrt(d) pivot steps on any simple d-polytope with n vertices. This is the first nontrivia…