pith. sign in

arxiv: 2510.24336 · v2 · pith:5KIURFGOnew · submitted 2025-10-28 · 🧮 math.CO

Semi-inducibility of 4-vertex graphs

classification 🧮 math.CO
keywords vertexedgesgraphsbluecolouredorderrespsemi-inducibility
0
0 comments X
read the original abstract

For a graph $H$ whose edges are coloured blue or red, the $H$-semi-inducibility problem asks for the maximum, over all graphs $G$ of given order $n$, of the number of injections from the vertex set of $H$ into the vertex set of $G$ that send red (resp. blue) edges of $H$ to edges (resp. non-edges) of $G$. We consider all possible 4-vertex non-complete graphs $H$ and essentially resolve all remaining cases except when $H$ is the 3-edge path coloured blue-blue-red in this order (or is equivalent to this case). Some of our proofs are computer-generated, using the flag algebra method of Razborov.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Fixed-density profiles for the semi-induced 4-vertex star

    math.CO 2026-06 unverdicted novelty 6.0

    For every fixed β in [0,1], the extremal S_{2,1}-densities are determined: the upper side completes a four-branch profile via prior work plus new low-density proof, while the lower side is achieved by a one-parameter ...