Source author record

Yury Person

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 Quantitative Methods

Catalog footprint

Research overview

14works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On universal hypergraphs

A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$ -uniform hypergraphs with maximum vertex degree bounded by $Δ$ and at most $n$ vertices any universal hypergraph has to contain $Ω(n^{r-r/Δ})$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$ -uniform hypergraphs with the optimal number of edges $O(n^{r-r/Δ})$ when $r$ is even, $r \mid Δ$ or $Δ=2$ . Further we generalize the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most $m$ edges and no isolated vertices to hypergraphs.

preprint2015arXiv

Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs

A uniform hypergraph $H$ is called $k$ -Ramsey for a hypergraph $F$ , if no matter how one colors the edges of $H$ with $k$ colors, there is always a monochromatic copy of $F$ . We say that $H$ is minimal $k$ -Ramsey for $F$ , if $H$ is $k$ -Ramsey for $F$ but every proper subhypergraph of $H$ is not. Burr, Erdős and Lovasz studied various parameters of minimal Ramsey graphs. In this paper we initiate the study of minimum degrees and codegrees of minimal Ramsey $3$ -uniform hypergraphs. We show that the smallest minimum vertex degree over all minimal $k$ -Ramsey $3$ -uniform hypergraphs for $K_t^{(3)}$ is exponential in some polynomial in $k$ and $t$ . We also study the smallest possible minimum codegrees over minimal $2$ -Ramsey $3$ -uniform hypergraphs.

preprint2015arXiv

On the minimum degree of minimal Ramsey graphs for multiple colours

A graph G is r-Ramsey for a graph H, denoted by G\rightarrow (H)_r, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. Let s_r(H) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H. The study of the parameter s_2 was initiated by Burr, Erdős, and Lovász in 1976 when they showed that for the clique s_2(K_k)=(k-1)^2. In this paper, we study the dependency of s_r(K_k) on r and show that, under the condition that k is constant, s_r(K_k) = r^2 polylog r. We also give an upper bound on s_r(K_k) which is polynomial in both r and k, and we determine s_r(K_3) up to a factor of log r.

preprint2015arXiv

Spanning structures and universality in sparse hypergraphs

In this paper the problem of finding various spanning structures in random hypergraphs is studied. We notice that a general result of Riordan [Spanning subgraphs of random graphs, Combinatorics, Probability & Computing 9 (2000), no. 2, 125-148] can be adapted from random graphs to random $r$ -uniform hypergaphs and provide sufficient conditions when a random $r$ -uniform hypergraph $\mathcal{H}^{(r)}(n,p)$ contains a given spanning structure a.a.s. We also discuss several spanning structures such as cube-hypergraphs, lattices, spheres and Hamilton cycles in hypergraphs. Moreover, we study universality, i.e. when does an $r$ -uniform hypergraph contain any hypergraph on $n$ vertices and with maximum vertex degree bounded by $Δ$ ? For $\mathcal{H}^{(r)}(n,p)$ it is shown that this holds for $p= ω\left((\ln n/n)^{1/Δ}\right)$ a.a.s. by combining approaches taken by Dellamonica, Kohayakawa, Rödl and Ruciński [An improved upper bound on the density of universal random graphs, Random Structures Algorithms 46 (2015), no. 2, 274-299] and of Ferber, Nenadov and Peter [Universality of random graphs and rainbow embedding, Random Structures Algorithms, to appear]. Furthermore it is shown that the random graph $G(n,p)$ for appropriate $p$ and explicit constructions of universal graphs due to Alon, Capalbo, Kohayakawa, Rödl, Ruciński and Szemerédi and Alon and Capalbo yield constructions of universal hypergraphs that are sparser than the random hypergraph $\mathcal{H}^{(r)}(n,p)$ with $p= ω\left((\ln n/n)^{1/Δ}\right)$ .

preprint2014arXiv

An algorithmic framework for obtaining lower bounds for random Ramsey problems

In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algorithmic perspective: we aim at providing an algorithm that finds the desired colouring with high probability. Our framework allows to reduce the probabilistic problem of whether the Ramsey property at hand holds for random (hyper)graphs with edge probability $p$ to a deterministic question of whether there exists a finite graph that forms an obstruction. In the second part of the paper we apply this framework to address and solve various open problems. In particular, we extend the result of Bohman, Frieze, Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs to the case of $2$ colors and to hypergraph cliques. As a corollary, this proves a matching lower bound for the result of Friedgut, Rödl and Schacht (2010) and, independently, Conlon and Gowers (2014+) for the classical Ramsey problem for hypergraphs in the case of cliques. Finally, we provide matching lower bounds for a proper-colouring version of anti-Ramsey problems introduced by Kohayakawa, Konstadinidis and Mota~(2014) in the case of cliques and cycles.

preprint2014arXiv

Keeping Avoider's graph almost acyclic

We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$ . By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non- $k$ -colorability game, and the $K_t$ -minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojaković, and Szabó. Moreover, we give a slight improvement for the lower bound in the non-planarity game.

preprint2014arXiv

Largest components in random hypergraphs

In this paper we consider $j$ -tuple-connected components in random $k$ -uniform hypergraphs (the $j$ -tuple-connectedness relation can be defined by letting two $j$ -sets be connected if they lie in a common edge and consider the transitive closure; the case $j=1$ corresponds to the common notion of vertex-connectedness). We determine that the existence of a $j$ -tuple-connected component containing $Θ(n^j)$ $j$ -sets in random $k$ -uniform hypergraphs undergoes a phase transition and show that the threshold occurs at edge probability $\tfrac{(k-j)!}{\binom{k}{j}-1}n^{j-k}$ . Our proof extends the recent short proof for the graph case by Krivelevich and Sudakov which makes use of a depth-first search to reveal the edges of a random graph. Our main original contribution is a "bounded degree lemma" which controls the structure of the component grown in the search process.

preprint2014arXiv

Powers of Hamilton cycles in pseudorandom graphs

We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph $G$ is $(\varepsilon,p,k,\ell)$ -pseudorandom if for all disjoint $X$ and $Y\subset V(G)$ with $|X|\ge\varepsilon p^kn$ and $|Y|\ge\varepsilon p^\ell n$ we have $e(X,Y)=(1\pm\varepsilon)p|X||Y|$ . We prove that for all $β>0$ there is an $\varepsilon>0$ such that an $(\varepsilon,p,1,2)$ -pseudorandom graph on $n$ vertices with minimum degree at least $βpn$ contains the square of a Hamilton cycle. In particular, this implies that $(n,d,λ)$ -graphs with $λ\ll d^{5/2 }n^{-3/2}$ contain the square of a Hamilton cycle, and thus a triangle factor if $n$ is a multiple of $3$ . This improves on a result of Krivelevich, Sudakov and Szabó [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.

preprint2013arXiv

On the multicolor Ramsey number of a graph with m edges

The multicolor Ramsey number $r_k(F)$ of a graph $F$ is the least integer $n$ such that in every coloring of the edges of $K_n$ by $k$ colors there is a monochromatic copy of $F$ . In this short note we prove an upper bound on $r_k(F)$ for a graph $F$ with $m$ edges and no isolated vertices of the form $k^{6km^{2/3}}$ addressing a question of Sudakov [ Adv. Math. 227 (2011), no. 1, 601--609]. Furthermore, the constant in the exponent in the case of bipartite $F$ and two colors is lowered so that $r_2(F)\le 2^{(1+o(1))2\sqrt{2m}}$ improving the result of Alon, Krivelevich and Sudakov [Combin. Probab. Comput. 12 (2003), no. 5--6, 477--494].

preprint2013arXiv

Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n^{-1+eps} for every eps>0. This partly answers a question of Dudek and Frieze [Random Structures Algorithms], who used a second moment method to show that tight Hamilton cycles exist even for p=omega(n)/n (r>2) where omega(n) tends to infinity arbitrary slowly, and for p=(e+o(1))/n (r>3). The method we develop for proving our result applies to related problems as well.

preprint2013arXiv

What is Ramsey-equivalent to a clique?

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K_k. A famous theorem of Nesetril and Rodl implies that any graph H which is Ramsey-equivalent to K_k must contain K_k. We prove that the only connected graph which is Ramsey-equivalent to K_k is itself. This gives a negative answer to the question of Szabo, Zumstein, and Zurcher on whether K_k is Ramsey-equivalent to K_k.K_2, the graph on k+1 vertices consisting of K_k with a pendent edge. In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s(H) be the smallest minimum degree over all Ramsey minimal graphs for H. The study of s(H) was introduced by Burr, Erdos, and Lovasz, where they show that s(K_k)=(k-1)^2. We prove that s(K_k.K_2)=k-1, and hence K_k and K_k.K_2 are not Ramsey-equivalent. We also address the question of which non-connected graphs are Ramsey-equivalent to K_k. Let f(k,t) be the maximum f such that the graph H=K_k+fK_t, consisting of K_k and f disjoint copies of K_t, is Ramsey-equivalent to K_k. Szabo, Zumstein, and Zurcher gave a lower bound on f(k,t). We prove an upper bound on f(k,t) which is roughly within a factor 2 of the lower bound.

preprint2012arXiv

A regularity lemma and twins in words

For a word $S$ , let $f(S)$ be the largest integer $m$ such that there are two disjoints identical (scattered) subwords of length $m$ . Let $f(n, Σ) = \min \{f(S): S \text{is of length} n, \text{over alphabet} Σ\}$ . Here, it is shown that $2f(n, \{0,1\}) = n-o(n)$ using the regularity lemma for words. I.e., any binary word of length $n$ can be split into two identical subwords (referred to as twins) and, perhaps, a remaining subword of length $o(n)$ . A similar result is proven for $k$ identical subwords of a word over an alphabet with at most $k$ letters.

preprint2011arXiv

An improved error term for minimum H-decompositions of graphs

We consider partitions of the edge set of a graph G into copies of a fixed graph H and single edges. Let ϕ_H(n) denote the minimum number p such that any n-vertex G admits such a partition with at most p parts. We show that ϕ_H(n)=ex(n,K_r)+Θ(biex(n,H)) for χ(H)>2, where biex(n,H) is the extremal number of the decomposition family of H. Since biex(n,H)=O(n^{2-γ}) for some γ>0 this improves on the bound ϕ_H(n)=ex(n,H)+o(n^2) by Pikhurko and Sousa [J. Combin. Theory Ser. B 97 (2007), 1041-1055]. In addition it extends a result of Özkahya and Person [J. Combin. Theory Ser. B, to appear].

preprint2011arXiv

On extremal hypergraphs for hamiltonian cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs, and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields a sufficient condition relying solely on the minimum vertex degree.

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.

Yury Person

Research overview

Is this your work?

14 publications

On universal hypergraphs

Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs

On the minimum degree of minimal Ramsey graphs for multiple colours

Spanning structures and universality in sparse hypergraphs

An algorithmic framework for obtaining lower bounds for random Ramsey problems

Keeping Avoider's graph almost acyclic

Largest components in random hypergraphs

Powers of Hamilton cycles in pseudorandom graphs

On the multicolor Ramsey number of a graph with m edges

Tight Hamilton cycles in random hypergraphs

What is Ramsey-equivalent to a clique?

A regularity lemma and twins in words

An improved error term for minimum H-decompositions of graphs

On extremal hypergraphs for hamiltonian cycles

See the researcher in context

Building this map preview