BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Christian Reiher contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Bermond and Thomassen conjectured that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex disjoint cycles. So far the conjecture was verified for $k\le 3$. Here we generalise the question asking for all outdegree sequences which force $k$ vertex disjoint cycles and give the full answer for $k\le 2$.
Given positive integers $n\ge s$, we let ${\mathrm{ex}}(n,s)$ denote the maximum number of edges in a triangle-free graph $G$ on $n$ vertices with $α(G)\le s$. In the early sixties Andrásfai conjectured that for $n/3<s<n/2$ the function ${\mathrm{ex}}(n, s)$ is piecewise quadratic with critical values at $s/n={k}/({3k-1})$. We confirm that this is indeed the case whenever $s/n$ is slightly larger than a critical value, thus determining ${\mathrm{ex}}(n,s)$ for all $n$ and $s$ such that $s/n\in [{k}/({3k-1}), {k}/({3k-1})+γ_k]$, where $γ_k=Θ(k^{-6})$.
For every positive integer $t$ we construct a finite family of triple systems ${\mathcal M}_t$, determine its Turán number, and show that there are $t$ extremal ${\mathcal M}_t$-free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every ${\mathcal M}_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turán tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of ${\mathcal M}_t$ has exactly $t$ global maxima.
We show that every $k$-uniform hypergraph on $n$ vertices whose minimum $(k-2)$-degree is at least $(5/9+o(1))n^2/2$ contains a Hamiltonian cycle. A construction due to Han and Zhao shows that this minimum degree condition is optimal. The same result was proved independently by Lang and Sahueza-Matamala.
One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on $n$ vertices without independent sets of size $αn$, where $2/5\le α< 1/2$, are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai's work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs~$G$ on $n$ vertices with $α(G)\ge 3n/8$ and state a conjecture on the structure of the densest triangle-free graphs $G$ with $α(G) > n/3$. We remark that the case $α(G) \le n/3$ behaves differently, but due to the work of Brandt this situation is fairly well understood.
We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every $k\geq 1$ and sufficiently large $n$ already the minimum degree $δ(G)\ge\tfrac{k}{k+1}n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just $O(n)$ random edges ensures the presence of the $(k+1)$-st power of a Hamiltonian cycle with probability close to one.
We show that every $3$-uniform hypergraph $H=(V,E)$ with $|V(H)|=n$ and minimum pair degree at least $(4/5+o(1))n$ contains a squared Hamiltonian cycle. This may be regarded as a first step towards a hypergraph version of the Pósa-Seymour conjecture.
An important question in extremal graph theory raised by Vera T. Sós asks to determine for a given integer $t\ge 3$ and a given positive real number $δ$ the asymptotically supremal edge density $f_t(δ)$ that an $n$-vertex graph can have provided it contains neither a complete graph $K_t$ nor an independent set of size $δn$. Building upon recent work of Fox, Loh, and Zhao [The critical window for the classical Ramsey-Turán problem, Combinatorica 35 (2015), 435-476], we prove that if $δ$ is sufficiently small (in a sense depending on $t$), then \[ f_t(δ)= \begin{cases} \frac{3t-10}{3t-4}+δ-δ^2 & \text{ if $t$ is even,} \cr \frac{t-3}{t-1}+δ& \text{ if $t$ is odd.} \end{cases} \]
Confirming a conjecture of Vera T. Sós in a very strong sense, we give a complete solution to Turán's hypergraph problem for the Fano plane. That is we prove for $n\ge 8$ that among all $3$-uniform hypergraphs on $n$ vertices not containing the Fano plane there is indeed exactly one whose number of edges is maximal, namely the balanced, complete, bipartite hypergraph. Moreover, for $n=7$ there is exactly one other extremal configuration with the same number of edges: the hypergraph arising from a clique of order $7$ by removing all five edges containing a fixed pair of vertices. For sufficiently large values $n$ this was proved earlier by Füredi and Simonovits, and by Keevash and Sudakov, who utilised the stability method.
We give a short survey of problems and results on (1) diameter graphs and hypergraphs, and (2) geometric Ramsey theory. We also make some modest contributions to both areas. Extending a well known theorem of Kahn and Kalai which disproved Borsuk's conjecture, we show that for any integer $r\ge 2$, there exist $\varepsilon=\varepsilon(r)>0$ and $d_0=d_0(r)$ with the following property. For every $d\ge d_0$, there is a finite point set $P\subset\mathbb{R}^d$ of diameter $1$ such that no matter how we color the elements of $P$ with fewer than $(1+\varepsilon)^{\sqrt{d}}$ colors, we can always find $r$ points of the same color, any two of which are at distance $1$.