<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_001.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mover accent="true"><mi>F</mi><mo>→</mo></mover></math>
<tex-math>\vec F</tex-math>
</alternatives>
</inline-formula>, determine the maximum cardinality <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_002.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>e</mi><msub><mrow><mi>x</mi></mrow><mi>v</mi></msub><mrow><mo>(</mo><mrow><mover accent="true"><mi>F</mi><mo>→</mo></mover><mo>,</mo><msub><mrow><mover accent="true"><mi>Q</mi><mo>→</mo></mover></mrow><mi>n</mi></msub></mrow><mo>)</mo></mrow></mrow></math>
<tex-math>e{x_v}\left( {\vec F,{{\vec Q}_n}} \right)</tex-math>
</alternatives>
</inline-formula> of a subset U of the vertices of the oriented hypercube <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_003.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msub><mrow><mover accent="true"><mi>Q</mi><mo>→</mo></mover></mrow><mi>n</mi></msub></mrow></math>
<tex-math>{\vec Q_n}</tex-math>
</alternatives>
</inline-formula> such that the induced subgraph <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_004.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msub><mrow><mover accent="true"><mi>Q</mi><mo>→</mo></mover></mrow><mi>n</mi></msub><mrow><mo>[</mo> <mi>U</mi> <mo>]</mo></mrow></mrow></math>
<tex-math>{\vec Q_n}\left[ U \right]</tex-math>
</alternatives>
</inline-formula> does not contain any copy of <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_005.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mover accent="true"><mi>F</mi><mo>→</mo></mover></math>
<tex-math>\vec F</tex-math>
</alternatives>
</inline-formula>. We obtain the exact value of <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_006.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>e</mi><msub><mrow><mi>x</mi></mrow><mi>v</mi></msub><mrow><mo>(</mo><mrow><mover accent="true"><mrow><msub><mrow><mi>P</mi></mrow><mi>k</mi></msub><mo>,</mo></mrow><mo stretchy="true">→</mo></mover><mi> </mi><mover accent="true"><mrow><msub><mrow><mi>Q</mi></mrow><mi>n</mi></msub></mrow><mo stretchy="true">→</mo></mover></mrow><mo>)</mo></mrow></mrow></math>
<tex-math>e{x_v}\left( {\overrightarrow {{P_k},} \,\overrightarrow {{Q_n}} } \right)</tex-math>
</alternatives>
</inline-formula> for the directed path <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_007.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mi>P</mi></mrow><mi>k</mi></msub></mrow><mo stretchy="true">→</mo></mover></mrow></math>
<tex-math>\overrightarrow {{P_k}}</tex-math>
</alternatives>
</inline-formula>, the exact value of <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_008.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>e</mi><msub><mrow><mi>x</mi></mrow><mi>v</mi></msub><mrow><mo>(</mo><mrow><mover accent="true"><mrow><msub><mrow><mi>V</mi></mrow><mn>2</mn></msub></mrow><mo stretchy="true">→</mo></mover><mo>,</mo><mi> </mi><mover accent="true"><mrow><msub><mrow><mi>Q</mi></mrow><mi>n</mi></msub></mrow><mo stretchy="true">→</mo></mover></mrow><mo>)</mo></mrow></mrow></math>
<tex-math>e{x_v}\left( {\overrightarrow {{V_2}} ,\,\overrightarrow {{Q_n}} } \right)</tex-math>
</alternatives>
</inline-formula> for the directed cherry <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_009.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mi>V</mi></mrow><mn>2</mn></msub></mrow><mo stretchy="true">→</mo></mover></mrow></math>
<tex-math>\overrightarrow {{V_2}}</tex-math>
</alternatives>
</inline-formula> and the asymptotic value of <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_010.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>e</mi><msub><mrow><mi>x</mi></mrow><mi>v</mi></msub><mrow><mo>(</mo><mrow><mover accent="true"><mi>T</mi><mo stretchy="true">→</mo></mover><mo>,</mo><mover accent="true"><mrow><msub><mrow><mi>Q</mi></mrow><mi>n</mi></msub></mrow><mo stretchy="true">→</mo></mover></mrow><mo>)</mo></mrow></mrow></math>
<tex-math>e{x_v}\left( {\overrightarrow T ,\overrightarrow {{Q_n}} } \right)</tex-math>
</alternatives>
</inline-formula> for any directed tree <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausm-2021-0022_eq_011.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mover accent="true"><mi>T</mi><mo>→</mo></mover></math>
<tex-math>\vec T</tex-math>
</alternatives>
</inline-formula>.</p>
</abstract>

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph 


F→
\vec F

, determine the maximum cardinality 


exv(F→,Q→n)
e{x_v}\left( {\vec F,{{\vec Q}_n}} \right)

 of a subset U of the vertices of the oriented hypercube 


Q→n
{\vec Q_n}

 such that the induced subgraph 


Q→n[ U ]
{\vec Q_n}\left[ U \right]

 does not contain any copy of 


F→
\vec F

. We obtain the exact value of 


exv(Pk,→ Qn→)
e{x_v}\left( {\overrightarrow {{P_k},} \,\overrightarrow {{Q_n}} } \right)

 for the directed path 


Pk→
\overrightarrow {{P_k}}

, the exact value of 


exv(V2→, Qn→)
e{x_v}\left( {\overrightarrow {{V_2}} ,\,\overrightarrow {{Q_n}} } \right)

 for the directed cherry 


V2→
\overrightarrow {{V_2}}

 and the asymptotic value of 


exv(T→,Qn→)
e{x_v}\left( {\overrightarrow T ,\overrightarrow {{Q_n}} } \right)

 for any directed tree 


T→
\vec T

.

Vertex Turán problems for the oriented hypercube

Lab. of Combinatorial and Geometric Structures

Acta Universitatis Sapientiae, Mathematica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Vertex Turán problems for the oriented hypercube"}

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph 


F→
\vec F

, determine the maximum cardinality...

Vertex Turán problems for the oriented hypercube

Publié en ligne: 30 déc. 2021

Pages: 356 - 366

DOI: https://doi.org/10.2478/ausm-2021-0022

Mots clés
vertex Turán, hypercube, extremal set theory

© 2021 Dániel Gerbner et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Vertex Turán problems for the oriented hypercube

Publié en ligne: 30 déc. 2021

Pages: 356 - 366

DOI: https://doi.org/10.2478/ausm-2021-0022

Mots clésvertex Turán, hypercube, extremal set theory

© 2021 Dániel Gerbner et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Mots clés
vertex Turán, hypercube, extremal set theory