Source author record

Liana Yepremyan

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

14works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Rainbow Turán number of clique subdivisions

We show that for any integer $t\geq 2$ , every properly edge-coloured graph on $n$ vertices with more than $n^{1+o(1)}$ edges contains a rainbow subdivision of $K_t$ . Note that this bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Turán numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting.

preprint2020arXiv

Full rainbow matchings in equivalence relations

We show that if a multigraph $G$ with maximum edge-multiplicity of at most $\frac{\sqrt{n}}{\log^2 n}$ , is edge-coloured by $n$ colours such that each colour class is a disjoint union of cliques with at least $2n + o(n)$ vertices, then it has a full rainbow matching, that is, a matching where each colour appears exactly once. This asymptotically solves a question raised by Clemens, Ehrenmüller and Pokrovskiy, and is related to problems on algebras of sets studied by Grinblat in [Grinblat 2002].

preprint2020arXiv

Linear cycles of consecutive lengths

A well-known result of Verstraëte \cite{V00} shows that for each integer $k\geq 2$ every graph $G$ with average degree at least $8k$ contains cycles of $k$ consecutive even lengths, the shortest of which is at most twice the radius of $G$ . We establish two extensions of Verstraëte's result for linear cycles in linear $r$ -uniform hypergraphs. We show that for any fixed integers $r\geq 3,k\geq 2$ , there exist constants $c_1=c_1(r)$ and $c_2=c_2(r,k)$ , such that every linear $r$ -uniform hypergraph $G$ with average degree $d(G)\geq c_1 k$ contains linear cycles of $k$ consecutive even lengths, the shortest of which is at most $2\lceil \frac{ \log n}{\log (d(G)/k)-c_2}\rceil$ . In particular, as an immediate corollary, we retrieve the current best known upper bound on the linear Turán number of $C^r_{2k}$ with improved coefficients. Furthermore, we show that for any fixed integers $r\geq 3,k\geq 2$ , there exist constants $c_3=c_3(r)$ and $c_4=c_4(r)$ such that every $n$ -vertex linear $r$ -uniform graph with average degree $d(G)\geq c_3k$ , contains linear cycles of $k$ consecutive lengths, the shortest of which has length at most $6\lceil \frac{\log n}{\log (d(G)/k)-c_4} \rceil +6$ . Both the degree condition and the shortest length among the cycles guaranteed are best possible up to a constant factor.

preprint2020arXiv

New bounds for Ryser's conjecture and related problems

A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser-Brualdi-Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$ . In this paper we prove the existence of a transversal of order $n-O(\log{n}/\log{\log{n}})$ , improving the celebrated bound of $n-O(\log^2n)$ by Hatami and Shor. Our approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. We obtain a new lower bound on a 40 year old conjecture of Brouwer on the maximum matching in Steiner triple systems, showing that every such system of order $n$ is guaranteed to have a matching of size $n/3-O(\log{n}/\log{\log{n}})$ . This substantially improves the current best result of Alon, Kim and Spencer which has the error term of order $n^{1/2+o(1)}$ . Finally, we also show that $O(n\log{n}/\log{\log{n}})$ many symbols in Latin arrays suffice to guarantee a full transversal, improving on previously known bound of $n^{2-\varepsilon}$ . The proofs combine in a novel way the semirandom method together with the robust expansion properties of edge coloured pseudorandom graphs to show the existence of a rainbow matching covering all but $O(\log n/\log{\log{n}})$ vertices. All previous results, based on the semi-random method, left uncovered at least $Ω(n^α)$ (for some constant $α$ ) vertices.

preprint2020arXiv

Notes on Tree- and Path-chromatic Number

Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger's Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwiger's Conjecture, we give a short proof that every $K_5$ -minor-free graph has tree-chromatic number at most $4$ , which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.

preprint2020arXiv

Random Turán theorem for hypergraph cycles

Given $r$ -uniform hypergraphs $G$ and $H$ the Turán number $\rm ex(G, H)$ is the maximum number of edges in an $H$ -free subgraph of $G$ . We study the typical value of $\rm ex(G, H)$ when $G=G_{n,p}^{(r)}$ , the Erdős-Rényi random $r$ -uniform hypergraph, and $H=C_{2\ell}^{(r)}$ , the $r$ -uniform linear cycle of length $2\ell$ . The case of graphs ( $r=2$ ) is a longstanding open problem that has been investigated by many researchers. We determine $\rm ex(G_{n,p}^{(r)}, C_{2\ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length decreases as $\ell$ grows. Our main technical contribution is a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan. The novelty is that the supersaturation result depends on the codegree of some pairs of vertices in the underlying hypergraph. This approach could be used to prove similar results for other hypergraphs $H$ .

preprint2018arXiv

On the number of symbols that forces a transversal

Akbari and Alipour conjectured that any Latin array of order $n$ with at least $n^2/2$ symbols contains a transversal. We confirm this conjecture for large $n$ , and moreover, we show that $n^{399/200}$ symbols suffice.

preprint2017arXiv

Supersaturation of Even Linear Cycles in Linear Hypergraphs

A classic result of Erdős and, independently, of Bondy and Simonovits says that the maximum number of edges in an $n$ -vertex graph not containing $C_{2k}$ , the cycle of length $2k$ , is $O( n^{1+1/k})$ . Simonovits established a corresponding supersaturation result for $C_{2k}$ 's, showing that there exist positive constants $C,c$ depending only on $k$ such that every $n$ -vertex graph $G$ with $e(G)\geq Cn^{1+1/k}$ contains at least $c\left(\frac{e(G)}{v(G)}\right)^{2k}$ many copies of $C_{2k}$ , this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper, we extend Simonovits' result to a supersaturation result of $r$ -uniform linear cycles of even length in $r$ -uniform linear hypergraphs. Our proof is self-contained and includes the $r=2$ case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.

preprint2015arXiv

Complete graph immersions and minimum degree

An immersion of a graph H in another graph G is a one-to-one mapping phi:V(H)->V(G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P_{uv} corresponding to the edge uv has endpoints phi(u) and phi(v). The immersion is strong if the paths P_{uv} are internally disjoint from phi(V(H)). We prove that every simple graph of minimum degree at least 11t+7 contains a strong immersion of the complete graph K_t. This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al.

preprint2015arXiv

Sparse halves in dense triangle-free graphs

Erdős conjectured that every triangle-free graph $G$ on $n$ vertices contains a set of $\lfloor n/2 \rfloor$ vertices that spans at most $n^2 /50$ edges. Krivelevich proved the conjecture for graphs with minimum degree at least $\frac{2}{5}n$ . Keevash and Sudakov improved this result to graphs with average degree at least $\frac{2}{5}n$ . We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least $\frac{5}{14}n$ and for graphs with average degree at least $(\frac{2}{5} - \varepsilon)n$ for some absolute $\varepsilon >0$ . Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.

preprint2015arXiv

The Characterization of planar, 4-connected, K_{2,5}-minor-free graphs

We show that every planar, 4-connected, K2;5-minor- free graph is the square of a cycle of even length at least six.

preprint2015arXiv

The extremal function for disconnected minors

For a graph $H$ let $c(H)$ denote the supremum of $|E(G)|/|V(G)|$ taken over all non-null graphs $G$ not containing $H$ as a minor. We show that $c(H) \leq \frac{|V(H)|+\mathrm{comp}(H)}{2}-1,$ when $H$ is a union of cycles, verifying conjectures of Reed and Wood, and Harvey and Wood. We derive the above result from a theorem which allows us to find two vertex disjoint subgraphs with prescribed densities in a sufficiently dense graph, which might be of independent interest.

preprint2015arXiv

Turán Number of Generalized Triangles

The family $Σ_r$ consists of all $r$ -graphs with three edges $D_1,D_2,D_3$ such that $|D_1\cap D_2|=r-1$ and $D_1 \triangle D_2 \subseteq D_3$ . A generalized triangle, $\mathcal{T}_r \in Σ_r$ is an $r$ -graph on $\{1,2,\ldots,2r-1\}$ with three edges $D_1, D_2, D_3$ , such that $D_1=\{1,2,\dots,r-1, r\}, D_2= \{1, 2, \dots, r-1, r+1 \}$ and $D_3 = \{r, r+1, \dots, 2r-1\}.$ Frankl and Füredi conjectured that for all $r\geq 4$ , $ex(n,Σ_r) = ex(n,\mathcal{T}_r )$ for all sufficiently large $n$ and they also proved it for $r=3$ . Later, Pikhurko showed that the conjecture holds for $r=4$ . In this paper we determine $ex(n,\mathcal{T}_5)$ and $ex(n,\mathcal{T}_6)$ for sufficiently large $n$ , proving the conjecture for $r=5,6$ .

preprint2015arXiv

Turán numbers of extensions

The extension of an $r$ -uniform hypergraph $G$ is obtained from it by adding for every pair of vertices of $G$ , which is not covered by an edge in $G$ , an extra edge containing this pair and $r-2$ new vertices. Keevash and Sidorenko~ have previously determined Turán densities of two families of hypergraph extensions. We determine the Turán numbers for these families, using classical stability techniques and new tools introduced in our earlier paper.

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.

Liana Yepremyan

Research overview

Is this your work?

14 publications

Rainbow Turán number of clique subdivisions

Full rainbow matchings in equivalence relations

Linear cycles of consecutive lengths

New bounds for Ryser's conjecture and related problems

Notes on Tree- and Path-chromatic Number

Random Turán theorem for hypergraph cycles

On the number of symbols that forces a transversal

Supersaturation of Even Linear Cycles in Linear Hypergraphs

Complete graph immersions and minimum degree

Sparse halves in dense triangle-free graphs

The Characterization of planar, 4-connected, K_{2,5}-minor-free graphs

The extremal function for disconnected minors

Turán Number of Generalized Triangles

Turán numbers of extensions

See the researcher in context

Building this map preview