wovepaper — the arXiv observatory

papers

Publications (24)

math.CO2014

A problem of Erdos and Sos on 3-graphs

Roman Glebov, Daniel Kral, Jan Volec

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, whe…

math.CO2011

On covering expander graphs by Hamilton cycles

Roman Glebov, Michael Krivelevich, Tibor SzabÃ³

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…

math.CO2015

On the Concentration of the Domination Number of the Random Graph

Roman Glebov, Anita Liebenau, Tibor SzabÃ³

In this paper we study the behaviour of the domination number of the ErdÅs-RÃ©nyi random graph $G (n, p)$ . Extending a result of Wieland and Godbole we show that the domin…

math.CO2019

Compactness and finite forcibility of graphons

Roman Glebov, Daniel Kral, Jan Volec

Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons deter…

math.CO2018

Infinite dimensional finitely forcible graphon

Roman Glebov, Tereza Klimosova, Daniel Kral

Graphons are analytic objects associated with convergent sequences of dense graphs. Finitely forcible graphons, i.e., those determined by finitely many subgraph densities, are of p…

math.CO2015

On the maximum number of Latin transversals

Roman Glebov, Zur Luria

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…

math.CO2013

Building spanning trees quickly in Maker-Breaker games

Dennis Clemens, Asaf Ferber, Roman Glebov +2

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…

math.CO2012

Biased Games On Random Boards

Asaf Ferber, Roman Glebov, Michael Krivelevich +1

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 pla…

cs.DM2016

Densities in large permutations and parameter testing

Roman Glebov, Carlos Hoppen, Tereza Klimosova +3

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 permuta…

math.CO2017

Virtually fibering random right-angled Coxeter groups

Gonzalo Fiz Pontiveros, Roman Glebov, Ilan Karpas

We show that the Right-Angled Coxeter group $C = C (G)$ associated to a random graph $G \sim G (n, p)$ with $\frac{l o g n + l o g l o g n + I ¨ ( 1 )}{n} \leq p < 1 - I ¨ (n^{- 2})$ virtu…

math.CO2016

The number of Hamiltonian decompositions of regular graphs

Roman Glebov, Zur Luria, Benny Sudakov

A Hamilton cycle in a graph $I^$ is a cycle passing through every vertex of $I^$ . A Hamiltonian decomposition of $I^$ is a partition of its edge set into disjoint Hamilton cycles.…

math.CO2013

Conflict-free coloring of graphs

Roman Glebov, Tibor SzabÃ³, GÃ¡bor Tardos

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-fr…

math.CO2011

Extremal graphs for clique-paths

Roman Glebov

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…

math.CO2022

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

Shoni Gilboa, Roman Glebov, Dan Hefetz +2

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 i…

math.CO2020

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Roman Glebov, Zur Luria, Michael Simkin

Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2 n}$ or the co…

math.CO2019

Colouring set families without monochromatic k-chains

Shagnik Das, Roman Glebov, Benny Sudakov +1

A coloured version of classic extremal problems dates back to ErdÅs and Rothschild, who in 1974 asked which $n$ -vertex graph has the maximum number of 2-edge-colourings without mo…

math.CO2014

The threshold probability for long cycles

Roman Glebov, Humberto Naves, Benny Sudakov

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

math.CO2012

How many colors guarantee a rainbow matching?

Roman Glebov, Benny Sudakov, Tibor SzabÃ³

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 f…

math.CO2011

Bijective mapping preserving intersecting antichains for k-valued cubes

Roman Glebov

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…

math.CO2016

Finitely forcible graphons and permutons

Roman Glebov, Andrzej Grzesik, Tereza Klimosova +1

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…

math.CO2011

On extremal hypergraphs for hamiltonian cycles

Roman Glebov, Yury Person, Wilma Weps

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…

math.CO2017

Densities of 3-vertex graphs

Roman Glebov, Andrzej Grzesik, Ping Hu +3

Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadru…

math.CO2014

Comparable pairs in families of sets

Noga Alon, Shagnik Das, Roman Glebov +1

Given a family $F$ of subsets of $[n]$ , we say two sets $A, B \in F$ are comparable if $A \subset B$ or $B \subset A$ . Sperner's celebrated theorem gives the si…

math.CO2013

The biased odd cycle game

Asaf Ferber, Roman Glebov, Michael Krivelevich +4

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$ . We prove that for every $I^´ > 0$ and large enough $n$ , there exists a constant $k$ f…