Source author record

Vojtěch Rödl

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

ResearcherUnclaimed source record

math.CO Computational Complexity

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Independence number of hypergraphs under degree conditions

A well-known result of Ajtai et al. from 1982 states that every $k$ -graph $H$ on $n$ vertices, with girth at least five, and average degree $t^{k-1}$ contains an independent set of size $c n (\log t)^{1/(k-1)}/t$ for some $c>0$ . In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3 and 4. Our work is motivated by a problem of Lo and Zhao, who asked for $k\ge 4$ , how large of an independent set a $k$ -graph $H$ on $n$ vertices necessarily has when its maximum $(k-2)$ -degree $Δ_{k-2}(H)\le dn$ . (The corresponding problem with respect to $(k-1)$ -degrees was solved by Kostochka, Mubayi, and Varstraëte [Random Structures & Algorithms 44, 224--239, 2014].) In this paper we show that every $k$ -graph $H$ on $n$ vertices with $Δ_{k-2}(H)\le dn$ contains an independent set of size $c (\frac nd \log\log \frac nd)^{1/(k-1)}$ , and under additional conditions, an independent set of size $c (\frac nd \log \frac nd)^{1/(k-1)}$ . The former assertion gives a new upper bound for the $(k-2)$ -degree Turán density of complete $k$ -graphs.

preprint2021arXiv

Colourful matchings

Suppose a committee consisting of three members has to match $n$ candidates to $n$ different positions. Each member of the committee proposes a matching, however the proposed matchings totally disagree, i.e., every candidate is matched to three different positions according to three committee members. All three committee members are very competitive and want to push through as many of their suggestions as possible. Can a committee always find a compromise -- a matching of candidates to positions such that for every committee member a third of all candidates are assigned according to that committee member suggestion? We will consider an asymptotic version of this question and several other variants of similar problem. As an application we will consider an embedding problem -- in particular which configurations large Steiner systems always need to contain.

preprint2020arXiv

On Hamiltonian cycles in hypergraphs with dense link graphs

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.

preprint2020arXiv

On local Turán problems

Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a $3$ -uniform hypergraph $\mathcal{F}$ on $n$ vertices in which any five vertices span at least one edge, prove that $|\mathcal{F}| \ge (1/4 -o(1))\binom{n}{3}$ . The construction showing that this bound would be best possible is simply $\binom{X}{3} \cup \binom{Y}{3}$ where $X$ and $Y$ evenly partition the vertex set. This construction has the following more general $(2p+1, p+1)$ -property: any set of $2p+1$ vertices spans a complete sub-hypergraph on $p+1$ vertices. One of our main results says that, quite surprisingly, for all $p>2$ the $(2p+1,p+1)$ -property implies the conjectured lower bound.

preprint2017arXiv

Borsuk and Ramsey type questions in Euclidean space

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$ .

preprint2016arXiv

Discrepancy and Eigenvalues of Cayley Graphs

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.

preprint2016arXiv

Embedding tetrahedra into quasirandom hypergraphs

We investigate extremal problems for quasirandom hypergraphs. We say that a $3$ -uniform hypergraph $H=(V,E)$ is $(d,η)$ -quasirandom if for any subset $X\subseteq V$ and every set of pairs $P\subseteq V\times V$ the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being a hyperedge of $H$ is in the interval $d|X||P|\pmη|V|^3$ . We show that for any $\varepsilon>0$ there exists $η>0$ such that every sufficiently large $(1/2+\varepsilon,η)$ -quasirandom hypergraph contains a tetrahedron, i.e., four vertices spanning all four hyperedges. A known random construction shows that the density $1/2$ is best possible. This result is closely related to a question of Erdős, whether every weakly quasirandom $3$ -uniform hypergraph $H$ with density bigger than $1/2$ , i.e., every large subset of vertices induces a hypergraph with density bigger than $1/2$ , contains a tetrahedron.

preprint2016arXiv

Note on Ramsey theorem for posets with linear extensions

In this note we consider a Ramsey type result for partially ordered sets. In particular, we give an alternative short proof of a theorem for a posets with multiple linear extensions recently obtained by Solecki and Zhao.

preprint2016arXiv

Packing minor-closed families of graphs into complete graphs

Motivated by a conjecture of Gyárfás, recently Böttcher, Hladký, Piguet, and Taraz showed that every collection $T_1,\dots,T_t$ of trees on $n$ vertices with $\sum_{i=1}^te(T_i)\leq \binom{n}{2}$ and with bounded maximum degree, can be packed into the complete graph on $(1+o(1))n$ vertices. We generalise this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor-closed class of graphs.

preprint2015arXiv

Hedgehogs are not colour blind

We exhibit a family of $3$ -uniform hypergraphs with the property that their $2$ -colour Ramsey numbers grow polynomially in the number of vertices, while their $4$ -colour Ramsey numbers grow exponentially. This is the first example of a class of hypergraphs whose Ramsey numbers show a strong dependence on the number of colours.

preprint2013arXiv

Extremal results in random graphs

According to Paul Erdős [Some notes on Turán's mathematical work, J. Approx. Theory 29 (1980), page 4] it was Paul Turán who "created the area of extremal problems in graph theory". However, without a doubt, Paul Erdős popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this field can be traced back to Paul Erdős, Paul Turán, as well as their collaborators and students. Paul Erdős also established the probabilistic method in discrete mathematics, and in collaboration with Alfréd Rényi, he started the systematic study of random graphs. We shall survey recent developments at the interface of extremal combinatorics and random graph theory.

preprint2013arXiv

The complexity of proving that a graph is Ramsey

We say that a graph with $n$ vertices is $c$ -Ramsey if it does not contain either a clique or an independent set of size $c \log n$ . We define a CNF formula which expresses this property for a graph $G$ . We show a superpolynomial lower bound on the length of resolution proofs that $G$ is $c$ -Ramsey, for every graph $G$ . Our proof makes use of the fact that every Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.

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.

Vojtěch Rödl

Research overview

Is this your work?

12 publications

Independence number of hypergraphs under degree conditions

Colourful matchings

On Hamiltonian cycles in hypergraphs with dense link graphs

On local Turán problems

Borsuk and Ramsey type questions in Euclidean space

Discrepancy and Eigenvalues of Cayley Graphs

Embedding tetrahedra into quasirandom hypergraphs

Note on Ramsey theorem for posets with linear extensions

Packing minor-closed families of graphs into complete graphs

Hedgehogs are not colour blind

Extremal results in random graphs

The complexity of proving that a graph is Ramsey

See the researcher in context

Building this map preview