Source author record

Nina Kamčev

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Asymptotic enumeration of hypergraphs by degree sequence

We prove an asymptotic formula for the number of $k$ -uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we find a formula that is asymptotically equal to the number of $d$ -regular $k$ -uniform hypergraphs on $n$ vertices provided that $dn\le c\binom{n}{k}$ for a constant $c>0$ , and $3 \leq k < n^C$ for any $C<1/9.$ Our results relate the degree sequence of a random $k$ -uniform hypergraph to a simple model of nearly independent binomial random variables, thus extending the recent results for graphs due to the second and third author.

preprint2020arXiv

Properly colored Hamilton cycles in Dirac-type hypergraphs

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 + γ)n$ , $γ>0$ , and $n$ is sufficiently large, then any edge coloring $ϕ$ satisfying appropriate local constraints yields a properly colored tight Hamilton cycle in $H$ . Similar results for loose cycles are also shown.

preprint2020arXiv

The Kőnig Graph Process

Say that a graph G has property $\mathcal{K}$ if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set $N:= \binom{n}{2}$ and let $e_1, e_2, \dots e_{N}$ be a uniformly random ordering of the edges of $K_n$ , with $n$ an even integer. Let $G_0$ be the empty graph on $n$ vertices. For $m \geq 0$ , $G_{m+1}$ is obtained from $G_m$ by adding the edge $e_{m+1}$ exactly if $G_m \cup \{ e_{m+1}\}$ has property $\mathcal{K}$ . We analyse the behaviour of this process, focusing mainly on two questions: What can be said about the structure of $G_N$ and for which $m$ will $G_m$ contain a perfect matching?

preprint2016arXiv

Anagram-free colorings of graphs

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_{2k}$ such that $r_{k+1} \dots r_{2k}$ is a permutation of the block $r_1 r_2\dots r_k$ . Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan, we consider a natural generalisation of anagram-free sequences for graph colorings. A coloring of the vertices of a given graph $G$ is called anagram-free if the sequence of colors on any path in $G$ is anagram-free. We call the minimal number of colors needed for such a coloring the anagram-chromatic number of $G$ . In this paper we study the anagram-chromatic number of several classes of graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly, we show that there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we basically give each vertex a separate color.

preprint2016arXiv

Bounded colorings of multipartite graphs and hypergraphs

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 Erd\H os and has been extensively studied since then. Recently it was extended to the hypergraph setting by Dudek, Frieze and Ruciński. We generalize these results, giving sufficient local (resp. global) restrictions on the colorings which guarantee a properly colored (resp. rainbow) copy of a given hypergraph $G$ . We also study multipartite analogues of these questions. We give (up to a constant factor) optimal sufficient conditions for a coloring $c$ of the complete balanced $m$ -partite graph to contain a properly colored or rainbow copy of a given graph $G$ with maximum degree $Δ$ . Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes $Δ\gg m$ and $Δ\ll m$ Our main tool is the framework of Lu and Székely for the space of random bijections, which we extend to product spaces.

preprint2015arXiv

Some Remarks on Rainbow Connectivity

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. Rainbow edge (vertex) connectivity of a graph $G$ is the smallest number of colours needed for a rainbow edge (vertex) colouring of $G$ . In this paper we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones.

preprint2014arXiv

Generalised Knight's Tours

The problem of existence of closed knight's tours in $[n]^d$ , where $[n]=\{0, 1, \dots, n-1\}$ , was recently solved by Erde, Golénia, and Golénia. They raised the same question for a generalised, $(a, b)$ knight, which is allowed to move along any two axes of $[n]^d$ by $a$ and $b$ unit lengths respectively. Given an even number $a$ , we show that the $[n]^d$ grid admits an $(a, 1)$ knight's tour for sufficiently large even side length $n$ .

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.