A rainbow version of Mantel's Theorem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10423616" target="_blank" >RIV/00216208:11320/20:10423616 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=kCqgGSFk4p" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=kCqgGSFk4p</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.19086/aic.12043" target="_blank" >10.19086/aic.12043</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A rainbow version of Mantel's Theorem

Popis výsledku v původním jazyce

Mantel&apos;s Theorem asserts that a simple $n$ vertex graph with more than~$frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| &gt; ( frac{ 26 - 2 sqrt{7} }{81})n^2 approx 0.2557 n^2$ for $1 le i le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} in E(G_i)$ for $1 le i le 3$. We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi.

Název v anglickém jazyce

A rainbow version of Mantel's Theorem

Popis výsledku anglicky

Mantel&apos;s Theorem asserts that a simple $n$ vertex graph with more than~$frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| &gt; ( frac{ 26 - 2 sqrt{7} }{81})n^2 approx 0.2557 n^2$ for $1 le i le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} in E(G_i)$ for $1 le i le 3$. We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-21082S" target="_blank" >GA19-21082S: Grafy a jejich algebraické vlastnosti</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Advances in Combinatorics

ISSN

2517-5599

e-ISSN

—

Svazek periodika

2020

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

12

Strana od-do

1-12

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85085000869