Source author record

Benjamin Reiniger

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Perfect matchings and Hamiltonian cycles in the preferential attachment model

In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with $m$ random vertices selected with probabilities proportional to their current degrees. (Constant $m$ is the only parameter of the model.) We prove that if $m \ge 1{,}260$ , then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that $m \ge 29{,}500$ . One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are "older" (i.e. are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting---sometimes called uniform attachment---in which vertices are added one by one and each vertex connects to $m$ older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version.

preprint2016arXiv

The game of Overprescribed Cops and Robbers played on graphs

We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.

preprint2015arXiv

Chvátal-type results for degree sequence Ramsey numbers

A sequence of nonnegative integers $π=(d_1,d_2,...,d_n)$ is graphic if there is a (simple) graph $G$ of order $n$ having degree sequence $π$ . In this case, $G$ is said to realize or be a realization of $π$ . Given a graph $H$ , a graphic sequence $π$ is potentially $H$ -graphic if there is some realization of $π$ that contains $H$ as a subgraph. In this paper, we consider a degree sequence analogue to classical graph Ramsey numbers. For graphs $H_1$ and $H_2$ , the potential-Ramsey number $r_{pot}(H_1,H_2)$ is the minimum integer $N$ such that for any $N$ -term graphic sequence $π$ , either $π$ is potentially $H_1$ -graphic or the complementary sequence $\overlineπ=(N-1-d_N,\dots, N-1-d_1)$ is potentially $H_2$ -graphic. We prove that if $s\ge 2$ is an integer and $T_t$ is a tree of order $t> 7(s-2)$ , then $r_{pot}(K_s, T_t) = t+s-2.$ This result, which is best possible up to the bound on $t$ , is a degree sequence analogue to a classical 1977 result of Chvátal on the graph Ramsey number of trees vs. cliques. To obtain this theorem, we prove a sharp condition that ensures an arbitrary graph packs with a forest, which is likely to be of independent interest.

preprint2015arXiv

Coloring, sparseness, and girth

An $r$ -augmented tree is a rooted tree plus $r$ edges added from each leaf to ancestors. For $d,g,r\in\mathbb{N}$ , we construct a bipartite $r$ -augmented complete $d$ -ary tree having girth at least $g$ . The height of such trees must grow extremely rapidly in terms of the girth. Using the resulting graphs, we construct sparse non- $k$ -choosable bipartite graphs, showing that maximum average degree at most $2(k-1)$ is a sharp sufficient condition for $k$ -choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non- $k$ -colorable graphs and hypergraphs with any girth $g$ .

preprint2015arXiv

Dynamic coloring parameters for graphs with given genus

A proper vertex coloring of a graph $G$ is $r$ -dynamic if for each $v\in V(G)$ , at least $\min\{r,d(v)\}$ colors appear in $N_G(v)$ . In this paper we investigate $r$ -dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10-colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any $r$ in terms of the genus of the graph: for sufficiently large $r$ , every graph with genus $g$ is $r$ -dynamically $((r+1)(g+5)+3)$ -colorable when $g\leq2$ and $r$ -dynamically $((r+1)(2g+2)+3)$ -colorable when $g\geq3$ . Furthermore, each of these upper bounds for $r$ -dynamic $k$ -colorability also holds for $r$ -dynamic $k$ -choosability and for $r$ -dynamic $k$ -paintability. We develop a method to prove that certain configurations are reducible for each of the corresponding $r$ -dynamic parameters.

preprint2014arXiv

A note on list-coloring powers of graphs

Recently, Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$ th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $χ(G^k)$ unbounded and $χ_{\ell}(G^k)\geq c χ(G^k) \log χ(G^k)$ . We also provide an upper bound, $χ_{\ell}(G^k)<χ(G^k)^3$ for $k>1$ .

preprint2014arXiv

Large subposets with small dimension

Dorais asked for the maximum guaranteed size of a dimension $d$ subposet of an $n$ -element poset. A lower bound of order $\sqrt{n}$ was found by Goodwillie. We provide a sublinear upper bound for each $d$ . For $d=2$ , our bound is $n^{0.8295}$ .

preprint2014arXiv

The Game Saturation Number of a Graph

Given a family ${\mathcal F}$ and a host graph $H$ , a graph $G\subseteq H$ is ${\mathcal F}$ -saturated relative to $H$ if no subgraph of $G$ lies in ${\mathcal F}$ but adding any edge from $E(H)-E(G)$ to $G$ creates such a subgraph. In the ${\mathcal F}$ -saturation game on $H$ , players Max and Min alternately add edges of $H$ to $G$ , avoiding subgraphs in ${\mathcal F}$ , until $G$ becomes ${\mathcal F}$ -saturated relative to $H$ . They aim to maximize or minimize the length of the game, respectively; $\textrm{sat}_g({\mathcal F};H)$ denotes the length under optimal play (when Max starts). Let ${\mathcal O}$ denote the family of all odd cycles and ${\mathcal T}$ the family of $n$ -vertex trees, and write $F$ for ${\mathcal F}$ when ${\mathcal F}=\{F\}$ . Our results include $\textrm{sat}_g({\mathcal O};K_{2k})=k^2$ , $\textrm{sat}_g({\mathcal T};K_n)=\binom{n-2}{2}+1$ for $n\ge6$ , $\textrm{sat}_g(K_{1,3};K_n)=2\lfloor n/2 \rfloor$ for $n\ge8$ , $\textrm{sat}_g(K_{1,r+1};K_n)=\frac{rn}{2}-\frac{r^2}{8}+O(1)$ , and $|\textrm{sat}_g(P_4;K_n)-(4n-1)/5|\le 1$ . We also determine $\textrm{sat}_g(P_4;K_{m,n})$ ; with $m\ge n$ , it is $n$ when $n$ is even, $m$ when $n$ is odd and $m$ is even, and $m+\lfloor n/2 \rfloor$ when $mn$ is odd. Finally, we prove the lower bound $\textrm{sat}_g(C_4;K_{n,n})\ge\frac{1}{10.4}n^{13/12}-O(n^{35/36})$ . The results are very similar when Min plays first, except for the $P_4$ -saturation game on $K_{m,n}$ .

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.

Benjamin Reiniger

Research overview

Is this your work?

8 publications

Perfect matchings and Hamiltonian cycles in the preferential attachment model

The game of Overprescribed Cops and Robbers played on graphs

Chvátal-type results for degree sequence Ramsey numbers

Coloring, sparseness, and girth

Dynamic coloring parameters for graphs with given genus

A note on list-coloring powers of graphs

Large subposets with small dimension

The Game Saturation Number of a Graph

See the researcher in context

Building this map preview