Source author record

Roman Glebov

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

18works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the local structure of oriented graphs -- a case study in flag algebras

Let $G$ be an $n$ -vertex oriented graph. Let $t(G)$ (respectively $i(G)$ ) be the probability that a random set of $3$ vertices of $G$ spans a transitive triangle (respectively an independent set). We prove that $t(G) + i(G) \geq \frac{1}{9}-o_n(1)$ . Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if $H$ is sufficiently far from that construction, then $t(H) + i(H)$ is significantly larger than $\frac{1}{9}$ . We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.

preprint2016arXiv

Densities in large permutations and parameter testing

A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.

preprint2016arXiv

Finitely forcible graphons and permutons

We investigate when limits of graphs (graphons) and permutations (permutons) are uniquely determined by finitely many densities of their substructures, i.e., when they are finitely forcible. Every permuton can be associated with a graphon through the notion of permutation graphs. We find permutons that are finitely forcible but the associated graphons are not. We also show that all permutons that can be expressed as a finite combination of monotone permutons and quasirandom permutons are finitely forcible, which is the permuton counterpart of the result of Lovasz and Sos for graphons.

preprint2016arXiv

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph $Γ$ is a cycle passing through every vertex of $Γ$ . A Hamiltonian decomposition of $Γ$ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki's theorem from the 19th century, showing that a complete graph $K_n$ on an odd number of vertices $n$ has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every $r$ -regular $n$ -vertex graph $Γ$ with even degree $r=cn$ for some fixed $c>1/2$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this paper we address the natural question of estimating $H(Γ)$ , the number of such decompositions of $Γ$ . Our main result is that $H(Γ)=r^{(1+o(1))nr/2}$ . In particular, the number of Hamiltonian decompositions of $K_n$ is $n^{(1-o(1))n^2/2}$ .

preprint2015arXiv

On the Concentration of the Domination Number of the Random Graph

In this paper we study the behaviour of the domination number of the Erdős-Rényi random graph $\mathcal{G}(n,p)$ . Extending a result of Wieland and Godbole we show that the domination number of $\mathcal{G}(n,p)$ is equal to one of two values asymptotically almost surely whenever $p \gg \frac{\ln^2n}{\sqrt{n}}$ . The explicit values are exactly at the first moment threshold, that is where the expected number of dominating sets starts to tend to infinity. For small $p$ we also provide various non-concentration results which indicate why some sort of lower bound on the probability $p$ is necessary in our first theorem. Concentration, though not on a constant length interval, is proven for every $p\gg 1/n$ . These results show that unlike in the case of $p \gg \frac{\ln^2n}{\sqrt{n}}$ where concentration of the domination number happens around the first moment threshold, for $p = O(\ln n/n)$ it does so around the median. In particular, in this range the two are far apart from each other.

preprint2015arXiv

On the maximum number of Latin transversals

Let $T(n)$ denote the maximal number of transversals in an order- $n$ Latin square. Improving on the bounds obtained by McKay et al., Taranenko recently proved that $T(n) \leq \left((1+o(1))\frac{n}{e^2}\right)^{n}$ , and conjectured that this bound is tight. We prove via a probabilistic construction that indeed $T(n) = \left((1+o(1))\frac{n}{e^2}\right)^{n}$ . Until the present paper, no superexponential lower bound for $T(n)$ was known. We also give a simpler proof of the upper bound.

preprint2014arXiv

A problem of Erdos and Sos on 3-graphs

We show that for every positive epsilon there exist positive delta and n_0 such that every 3-uniform hypergraph on n>=n_0 vertices with the property that every k-vertex subset, where k>=delta*n, induces at least (1/4 + epsilon)*{k \choose 3} edges, contains K4- as a subgraph, where K4- is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdos and Sos. The constant 1/4 is the best possible.

preprint2014arXiv

Comparable pairs in families of sets

Given a family $\mathcal{F}$ of subsets of $[n]$ , we say two sets $A, B \in \mathcal{F}$ are comparable if $A \subset B$ or $B \subset A$ . Sperner's celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size. In this paper we study a complementary problem posed by Erdős and Daykin and Frankl in the early '80s. They asked for the maximum number of comparable pairs that can appear in a family of $m$ subsets of $[n]$ , a quantity we denote by $c(n,m)$ . We first resolve an old conjecture of Alon and Frankl, showing that $c(n,m) = o(m^2)$ when $m = n^{ω(1)} 2^{n/2}$ . We also obtain more accurate bounds for $c(n,m)$ for sparse and dense families, characterise the extremal constructions for certain values of $m$ , and sharpen some other known results.

preprint2014arXiv

The threshold probability for long cycles

For a given graph $G$ of minimum degree at least $k$ , let $G_p$ denote the random spanning subgraph of $G$ obtained by retaining each edge independently with probability $p=p(k)$ . We prove that if $p \ge \frac{\log k + \log \log k + ω_k(1)}{k}$ , where $ω_k(1)$ is any function tending to infinity with $k$ , then $G_p$ asymptotically almost surely contains a cycle of length at least $k+1$ . When we take $G$ to be the complete graph on $k+1$ vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

preprint2013arXiv

Building spanning trees quickly in Maker-Breaker games

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree, then Maker can win this game within n+1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide non-trivial examples of families of trees which Maker cannot build in n-1 moves.

preprint2013arXiv

Conflict-free coloring of graphs

We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős-Rényi random graph G(n,p) and give the asymptotics for p=omega(1/n). We also show that for p \geq 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

preprint2013arXiv

The biased odd cycle game

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$ . We prove that for every $δ>0$ and large enough $n$ , there exists a constant $k$ for which if $δ(G)\geq δn$ and $χ(G)\geq k$ , then Maker can build an odd cycle in the $(1:b)$ game for $b=O(\frac{n}{\log^2 n})$ . We also consider the analogous game where Maker and Breaker claim vertices instead of edges. This is a special case of the following well known and notoriously difficult problem due to Duffus, Łuczak and Rödl: is it true that for any positive constants $t$ and $b$ , there exists an integer $k$ such that for every graph $G$ , if $χ(G)\geq k$ , then Maker can build a graph which is not $t$ -colorable, in the $(1:b)$ Maker-Breaker game played on the vertices of $G$ ?

preprint2012arXiv

Biased Games On Random Boards

In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board $G\sim \gnp$. In Maker-Breaker games there are two players, denoted by Maker and Breaker. In each round, Maker claims one previously unclaimed edge of $G$ and Breaker responds by claiming $b$ previously unclaimed edges. We consider the Hamiltonicity game, the perfect matching game and the $k$ -vertex-connectivity game, where Maker's goal is to build a graph which possesses the relevant property. Avoider-Enforcer games are the reverse analogue of Maker-Breaker games with a slight modification, where the two players claim at least 1 and at least $b$ previously unclaimed edges per move, respectively, and Avoider aims to avoid building a graph which possesses the relevant property. Maker-Breaker games are known to be "bias-monotone", that is, if Maker wins the $(1,b)$ game, he also wins the $(1,b-1)$ game. Therefore, it makes sense to define the critical bias of a game, $b^*$ , to be the "breaking point" of the game. That is, Maker wins the $(1,b)$ game whenever $b\leq b^*$ and loses otherwise. An analogous definition of the critical bias exists for Avoider-Enforcer games: here, the critical bias of a game $b^*$ is such that Avoider wins the $(1,b)$ game for every $b > b^*$ , and loses otherwise. We prove that, for every $p=ω(\frac{\ln n}{n})$ , $G\sim\gnp$ is typically such that the critical bias for all the aforementioned Maker-Breaker games is asymptotically $b^*=\frac{np}{\ln n}$ . We also prove that in the case $p=Θ(\frac{\ln n}{n})$ , the critical bias is $b^*=Θ(\frac{np}{\ln n})$ . These results settle a conjecture of Stojaković and Szabó. For Avoider-Enforcer games, we prove that for $p=Ω(\frac{\ln n}{n})$ , the critical bias for all the aforementioned games is $b^*=Θ(\frac{np}{\ln n})$ .

preprint2012arXiv

How many colors guarantee a rainbow matching?

Given a coloring of the edges of a multi-hypergraph, a rainbow t-matching is a collection of t disjoint edges, each having a different color. In this note we study the problem of finding a rainbow $t$ -matching in an r-partite r-uniform multi-hypergraph whose edges are colored with f colors such that every color class is a matching of size t. This problem was posed by Aharoni and Berger, who asked to determine the minimum number of colors which guarantees a rainbow matching. We improve on the known upper bounds for this problem for all values of the parameters. In particular for every fixed r, we give an upper bound which is polynomial in t, improving the superexponential estimate of Alon. Our proof also works in the setting not requiring the hypergraph to be r-partite.

preprint2011arXiv

Bijective mapping preserving intersecting antichains for k-valued cubes

Generalizing a result of Miyakawa, Nozaki, Pogosyan and Rosenberg, we prove that there is a one-to-one correspondence between the set of intersecting antichains in a subset of the lower half of the k-valued n-cube and the set of intersecting antichains in the k-valued (n-1)-cube.

preprint2011arXiv

Extremal graphs for clique-paths

In this paper we deal with a Turán-type problem: given a positive integer n and a forbidden graph H, how many edges can there be in a graph on n vertices without a subgraph H? How does a graph look like if it has this extremal edge number? The forbidden graph in this article is a clique-path: a path of length k where each edge is extended to an r-clique, r >2. We determine both the extremal number and the extremal graphs for sufficiently large n.

preprint2011arXiv

On covering expander graphs by Hamilton cycles

The problem of packing Hamilton cycles in random and pseudorandom graphs has been studied extensively. In this paper, we look at the dual question of covering all edges of a graph by Hamilton cycles and prove that if a graph with maximum degree $Δ$ satisfies some basic expansion properties and contains a family of $(1-o(1))Δ/2$ edge disjoint Hamilton cycles, then there also exists a covering of its edges by $(1+o(1))Δ/2$ Hamilton cycles. This implies that for every $α>0$ and every $p \geq n^{α-1}$ there exists a covering of all edges of $G(n,p)$ by $(1+o(1))np/2$ Hamilton cycles asymptotically almost surely, which is nearly optimal.

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.

Roman Glebov

Research overview

Is this your work?

18 publications

On the local structure of oriented graphs -- a case study in flag algebras

Densities in large permutations and parameter testing

Finitely forcible graphons and permutons

The number of Hamiltonian decompositions of regular graphs

On the Concentration of the Domination Number of the Random Graph

On the maximum number of Latin transversals

A problem of Erdos and Sos on 3-graphs

Comparable pairs in families of sets

The threshold probability for long cycles

Building spanning trees quickly in Maker-Breaker games

Conflict-free coloring of graphs

The biased odd cycle game

Biased Games On Random Boards

How many colors guarantee a rainbow matching?

Bijective mapping preserving intersecting antichains for k-valued cubes

Extremal graphs for clique-paths

On covering expander graphs by Hamilton cycles

On extremal hypergraphs for hamiltonian cycles

See the researcher in context

Building this map preview