Nina Kamcev

activity

20152026

most citedSome Remarks on Rainbow Connectivity

12 citations · 15 across the 9 of their papers we have counts for

collaborators

13 papers

math.CO2026

Optimal Bounds on Spanning Tree Embeddings

Csongor Beke, Vladimir Bošković, Nina Kamčev +1

We prove that the number of labelled embeddings of any $n$ -vertex tree $T$ into an $n$ -vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1…

math.CO2023

Universal lower bound for community structure of sparse graphs

Vilhelm Agdur, Nina Kamčev, Fiona Skerman

We prove new lower bounds on the modularity of graphs. Specifically, the modularity of a graph $G$ with average degree $d ˉ$ is $Ω (d ˉ^{- 1/2})$ , under some mild assumptions…

math.PR2023

Increasing paths in random temporal graphs

Nicolas Broutin, Nina Kamčev, Gabor Lugosi

We consider random temporal graphs, a version of the classical Erdős--Rényi random graph G(n,p) where additionally, each edge has a distinct random time stamp, and connectivity is…

math.CO2023★ 1 cited

Canonical colourings in random graphs

Nina Kamčev, Mathias Schacht

Rödl and Ruciński (1990) established Ramsey's theorem for random graphs. In particular, for fixed integers $r$ , $ℓ \geq 2$ they showed that $\hat p_{K_\ell,r}(n)=n^{-\frac{2}{\el…

math.CO2022

Unavoidable patterns in locally balanced colourings

Nina Kamčev, Alp Müyesser

Which patterns must a two-colouring of $K_{n}$ contain if each vertex has at least $ε n$ red and $ε n$ blue neighbours? In this paper, we investigate this questio…

math.CO2021

On uncommon systems of equations

Nina Kamčev, Anita Liebenau, Natasha Morrison

A system of linear equations $L$ over $F_{q}$ is common if the number of monochromatic solutions to $L$ in any two-colouring of $F_{q}^{n}$ is asymptotically at least t…

math.CO2020

Properly colored Hamilton cycles in Dirac-type hypergraphs

Sylwia Antoniuk, Nina Kamčev, Andrzej Ruciński

We consider a robust variant of Dirac-type problems in $k$ -uniform hypergraphs. For instance, we prove that if $H$ is a $k$ -uniform hypergraph with minimum codegree at least $(1/2…

math.CO2019

The size Ramsey number of graphs with bounded treewidth

Nina Kamcev, Anita Liebenau, David R. Wood +1

A graph $G$ is Ramsey for a graph $H$ if every 2-colouring of the edges of $G$ contains a monochromatic copy of $H$ . We consider the following question: if $H$ has bounded treewidt…

math.CO2018

Another Note on Intervals in the Hales-Jewett Theorem

Nina Kamčev, Christoph Spiegel

The Hales-Jewett Theorem states that any $r$ -colouring of $[m]^{n}$ contains a monochromatic combinatorial line if $n$ is large enough. Shelah's proof of the theorem implies that for…

math.CO2018★ 2 cited

Intervals in the Hales-Jewett theorem

David Conlon, Nina Kamcev

The Hales-Jewett theorem states that for any $m$ and $r$ there exists an $n$ such that any $r$ -colouring of the elements of $[m]^{n}$ contains a monochromatic combinatorial line. We…

math.CO2016

Anagram-free colorings of graphs

Nina Kamčev, Tomasz Łuczak, Benny Sudakov

A sequence $S$ is called anagram-free if it contains no consecutive symbols $r_{1} r_{2} \dots r_{k} r_{k + 1} \dots r_{2 k}$ such that $r_{k + 1} \dots r_{2 k}$ is a permutation of the block $…

math.CO2016

Bounded colorings of multipartite graphs and hypergraphs

Nina Kamčev, Benny Sudakov, Jan Volec

Let $c$ be an edge-coloring of the complete $n$ -vertex graph $K_{n}$ . The problem of finding properly colored and rainbow Hamilton cycles in $c$ was initiated in 1976 by Bollobás and…

math.CO2015★ 12 cited

Some Remarks on Rainbow Connectivity

Nina Kamčev, Michael Krivelevich, Benny Sudakov

An edge (vertex) coloured graph is rainbow-connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colours.…