Pascal Su
YOU?
Author Swipe
View article: Mastermind with a linear number of queries
Mastermind with a linear number of queries Open
Since the 1960s Mastermind has been studied for the combinatorial and information theoretical interest the game has to offer. Many results have been discovered starting with Erdős and Rényi determining the optimal number of queries needed …
View article: Mastermind with a linear number of queries
Mastermind with a linear number of queries Open
Since the 1960s Mastermind has been studied for the combinatorial and information-theoretical interest the game has to offer. Many results have been discovered starting with Erdős and Rényi determining the optimal number of queries needed …
View article: An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability Open
We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 197…
View article: An O(n) time algorithm for finding Hamilton cycles with high probability
An O(n) time algorithm for finding Hamilton cycles with high probability Open
We design a randomized algorithm that finds a Hamilton cycle in $\mathcal{O}(n)$ time with high probability in a random graph $G_{n,p}$ with edge probability $p\ge C \log n / n$. This closes a gap left open in a seminal paper by Angluin an…
View article: The Chromatic Number of Dense Random Block Graphs
The Chromatic Number of Dense Random Block Graphs Open
The chromatic number $χ(G)$ of a graph $G$, that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same color, is a classic and extensively studied parameter. Here we …
View article: $K_r$-Factors in Graphs with Low Independence Number
$K_r$-Factors in Graphs with Low Independence Number Open
A classical result by Hajnal and Szemerédi from 1970 determines the minimal degree conditions necessary to guarantee for a graph to contain a $K_r$-factor. Namely, any graph on $n$ vertices, with minimum degree $δ(G) \ge \left(1-\frac{1}{r…
View article: Improved Bounds on the Multicolor Ramsey Numbers of Paths and Even Cycles
Improved Bounds on the Multicolor Ramsey Numbers of Paths and Even Cycles Open
We study the multicolor Ramsey numbers for paths and even cycles, $R_k(P_n)$ and $R_k(C_n)$, which are the smallest integers $N$ such that every coloring of the complete graph $K_N$ has a monochromatic copy of $P_n$ or $C_n$ respectively. …
View article: Improved bounds on the multicolor Ramsey numbers of paths and even cycles
Improved bounds on the multicolor Ramsey numbers of paths and even cycles Open
We study the multicolor Ramsey numbers for paths and even cycles, Rk(Pn) and Rk(Cn), which are the smallest integers N such that every coloring of the complete graph KN has a monochromatic copy of Pn or Cn respectively. For a long time, Rk…
View article: Improved bounds on the multicolor Ramsey numbers of paths and even cycles
Improved bounds on the multicolor Ramsey numbers of paths and even cycles Open
We study the multicolor Ramsey numbers for paths and even cycles, $R_k(P_n)$ and $R_k(C_n)$, which are the smallest integers $N$ such that every coloring of the complete graph $K_N$ has a monochromatic copy of $P_n$ or $C_n$ respectively. …
View article: Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees Open
Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however n…
View article: Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes
Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes Open
We investigate the nearest common ancestor (NCA) function in rooted trees. As the main conceptual contribution, the paper introduces universal trees for the NCA function: For a given family of rooted trees, an NCA-universal tree $S$ is a r…
View article: Bipartite Kneser Graphs are Hamiltonian
Bipartite Kneser Graphs are Hamiltonian Open
For integers $k\\geq 1$ and $n\\geq 2k+1$ the Kneser graph $K(n,k)$ has as\nvertices all $k$-element subsets of $[n]:=\\{1,2,\\ldots,n\\}$ and an edge between\nany two vertices (=sets) that are disjoint. The bipartite Kneser graph $H(n,k)$…