Zobrazeno 1 - 10
of 182
pro vyhledávání: '"Pokrovskiy, Alexey"'
In 1995, Erd\H{o}s and Gy\'{a}rf\'{a}s proved that in every $2$-edge-coloured complete graph on $n$ vertices, there exists a collection of $2\sqrt{n}$ monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured th
Externí odkaz:
http://arxiv.org/abs/2409.03623
We show that the edges of any $d$-regular graph can be almost decomposed into paths of length roughly $d$, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a $d$-regular graph
Externí odkaz:
http://arxiv.org/abs/2406.02514
Autor:
Draganić, Nemanja, Montgomery, Richard, Correia, David Munhá, Pokrovskiy, Alexey, Sudakov, Benny
An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C>0$ for which every $C
Externí odkaz:
http://arxiv.org/abs/2402.06603
A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_1, \ldots, H_m$ are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartran
Externí odkaz:
http://arxiv.org/abs/2308.11613
Publikováno v:
Journal of Combinatorial Theory, Series B, Volume 169, November 2024, Pages 507-541
Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to randomly embed $G$ into $H$ with good "spread". More precisely, for a wide
Externí odkaz:
http://arxiv.org/abs/2308.08535
A common problem in graph colouring seeks to decompose the edge set of a given graph into few similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald conjectured that the edges of every cubic graph on $4n$ vertices can be
Externí odkaz:
http://arxiv.org/abs/2210.11458
The Tur\'an density of an $r$-uniform hypergraph $\mathcal{H}$, denoted $\pi(\mathcal{H})$, is the limit of the maximum density of an $n$-vertex $r$-uniform hypergraph not containing a copy of $\mathcal{H}$, as $n \to \infty$. Denote by $\mathcal{C}_
Externí odkaz:
http://arxiv.org/abs/2209.08134
We prove that the family of graphs containing no cycle with exactly $k$-chords is $\chi$-bounded, for $k$ large enough or of form $\ell(\ell-2)$ with $\ell \ge 3$ an integer. This verifies (up to a finite number of values $k$) a conjecture of Aboulke
Externí odkaz:
http://arxiv.org/abs/2208.14860
Autor:
Pokrovskiy, Alexey
Recently Lau-Jeyaseeli-Shiu-Arumugam introduced the concept of the "Sudoku colourings" of graphs -- partial $\chi(G)$-colourings of $G$ that have a unique extension to a proper $\chi(G)$-colouring of all the vertices. They introduced the Sudoku numbe
Externí odkaz:
http://arxiv.org/abs/2206.08914
Autor:
Müyesser, Alp, Pokrovskiy, Alexey
A complete mapping of a group $G$ is a bijection $\phi\colon G\to G$ such that $x\mapsto x\phi(x)$ is also bijective. Hall and Paige conjectured in 1955 that a finite group $G$ has a complete mapping whenever $\prod_{x\in G} x$ is the identity in the
Externí odkaz:
http://arxiv.org/abs/2204.09666