≤$\leq$

# Dynamic In-context Learning with Conversational Models for Data Extraction
and Materials Property Prediction

Chinedu E. Ekuma<EMAIL_ADDRESS>Department of Physics, Lehigh University,
Bethlehem, PA 18015, USA

###### Abstract

The advent of natural language processing and large language models (LLMs) has
revolutionized the extraction of data from unstructured scholarly papers.
However, ensuring data trustworthiness remains a significant challenge. In
this paper, we introduce PropertyExtractor, an open-source tool that leverages
advanced conversational LLMs like Google gemini-pro and OpenAI gpt-4, blends
zero-shot with few-shot in-context learning, and employs engineered prompts
for the dynamic refinement of structured information hierarchies – enabling
autonomous, efficient, scalable, and accurate identification, extraction, and
verification of material property data. Our tests on material data demonstrate
precision and recall exceeding 93% with an error rate of approximately 10%,
highlighting the effectiveness and versatility of the toolkit. We apply
PropertyExtractor to generate a database of 2D material thicknesses, a
critical parameter for device integration. The rapid evolution of the field
has outpaced both experimental measurements and computational methods,
creating a significant data gap. Our work addresses this gap and showcases the
potential of PropertyExtractor as a reliable and efficient tool for the
autonomous generation of diverse material property databases, advancing the
field.

PropertyExtractor; large language models; autonomous data extraction; dynamic
zero-shot-few-shot in-context learning; 2D materials property; thickness

The advent of generative artificial intelligence, particularly through
advances in large language models (LLMs) and natural language processing
(NLP), represents a transformative shift in the ability to harness
unstructured data across diverse fields, such as material science. The
abundance of data, which includes journal articles, patents, and theses, could
be overwhelming for manual data extraction, especially due to the rapid pace
of publication and its voluminous nature. Efficiently extracting and utilizing
this information for material characterization and discovery remains a
significant challenge. Traditional methods for data extraction from
unstructured texts in materials science have relied on labor-intensive setups,
including the development of parsing rules and the identification of specific
phrases, necessitating extensive model fine-tuning and re-training. Such
processes are both resource-consuming and time-intensive, often resulting in
systems that are rigidly specialized for narrow tasks KONONOVA2021102155 ;
Gilligan2023 . Recent advancements in the generative pretrained transformer
series of LLMs, noted for their exceptional capabilities in generating
coherent and contextually relevant text, summarizing content, and identifying
relationships between concepts, offer a promising solution. These
conversational LLMs automate the extraction of relevant information from
extensive document collections, facilitating the creation of material property
databases and accelerating the discovery of new materials Polak2024 ;
D3DD00113J ; Dagdelen2024 .

Recent advancements in the field of materials science have significantly
benefited from the development of NLP techniques aimed at extracting valuable
information from unstructured research papers. These efforts have laid the
groundwork for sophisticated data analysis and extraction methods, allowing
researchers to glean insights that were previously inaccessible Polak2024 ;
D3DD00113J ; Gilligan2023 ; D3DD00019B . Despite these advances, challenges
remain in achieving high fidelity data and context-aware data extraction,
particularly when dealing with complex physical properties and diverse
scientific terminologies. Huang & Cole fine-tuned a BERT model on battery-
related publications to enhance a battery database, employing a “question and
answer” (Q/A) strategy to extract specific device-level information. However,
their method struggles with passages containing multiple device information
and requires extensive pre-training on battery research papers before fine-
tuning for the Q/A tasks doi:10.1021/acs.jcim.2c00035 . More recently, Zheng
et al. developed a prompt-engineering approach, ChemPrompt with ChatGPT,
focused on transforming text into tabular forms and summarizing scientific
papers, leveraging the vast pretraining corpus to create semi-structured
summaries doi:10.1021/jacs.3c05819 . Similarly, studies by Castro and Pimentel
explored ChatGPT’s baseline chemistry knowledge and found that without
advanced prompt engineering, the model’s performance was suboptimal on
straightforward chemistry tasks doi:10.1021/acs.jcim.3c00285 . The work of Xie
et al. expanded the use of LLMs in materials science, fine-tuning them on a
broad corpus for diverse tasks such as Q/A, inverse design, classification,
and regression Xie2023DARWIN . Despite these advancements, these approaches
often fail to extract structured representations of complex hierarchical
entity relationships and do not generalize beyond the limitations of the
pretraining corpus. Recent works also showed that the performance of LLM-based
architectures in extracting material property information can be improved via
engineered prompts Dagdelen2024 ; Polak2024 . While these advances have
significantly enhanced the structured information extraction of material
property data, there is still an inherent issue of scalability and
transferability, including challenges in extracting structured representations
of complex hierarchical entity relationships generalizing outside of the
pretraining corpus.

Figure 1: Summarized flowchart of the PropertyExtractor code for obtaining
structured dataset with a conversational large language model. The flow
diagram provides the basic ideas for each step of the process and illustrates
the integration with the API for obtaining unstructured scientific papers. A
more detailed flowchart is presented in Figure 2.

In this paper, we introduce a blended dynamic zero-shot-few-shot in-context
learning approach. Here, task-specific instructions, such as “Yes” and “No”
responses (zero-shot learning) are combined with non-prescriptive guidance
(few-shot learning) that dynamically incorporates accurately performed tasks
into the model, enhancing and providing a closed feedback loop for both
scalability and predictability. The concept of in-context learning (ICL) has
emerged as a central paradigm for task adaptation in LLMs
Dong2023InContextLearning , fundamentally enabling the model to adapt its
behavior based on provided examples rather than undergoing resource-intensive
fine-tuning of its internal parameters. ICL effectively leverages the
“context” embedded within the model’s prompt to adapt the LLM to specific
downstream tasks, spanning a spectrum from zero-shot learning (where no
additional examples are provided — task descriptive instructions) to few-shot
learning (where several examples are offered). Leveraging the inherent
semantic similarity, our approach dynamically selects contextually relevant
outcomes from a set of accurately prior predicted tasks, thereby enhancing
prompt engineering and scalability for the predictability of the large
language model-based toolkit. Such an approach is pivotal in materials
science, particularly for extracting critical property data such as those of
novel two-dimensional (2D) materials Novoselov2012 ; kastuar2022efficient ;
NAJMAEI2020110 ; Khanmohammadi2024 , which generally lack generalizable
property databases compared to conventional bulk materials.

We implement this approach in the open-source code, PropertyExtractor, a
Python-based computational framework designed to generate structured material
property datapoint quadruplets of material, property value, original unit,
method. It employs a sophisticated combination of engineered prompts and
dynamic zero-shot-few-shot in-context learning to identify data-rich
sentences, whether these appear within tables or as single or multiple data
values within text. This approach not only extracts data but also verifies its
accuracy, addressing common issues associated with factual inaccuracies
typically observed in large language model responses. PropertyExtractor
achieved significant improvements in model scalability, realizing a precision
of $\sim 96\%$, a recall of $94\%$, an accuracy of 90%, an F1-score of 95%,
and an error rate of $\sim$10% on a constrained dataset of the thickness of 2D
materials. These performance metrics surpass those reported in earlier studies
Polak2024 ; D3DD00113J ; Gilligan2023 , highlighting its potential utility in
both academic and industrial settings. Moreover, PropertyExtractor is designed
as a software and leverages online LLM APIs, which allow users to train
bespoke models without extensive knowledge of the internal workings of LLMs or
Python skill. The user may simply treat the PropertyExtractor architecture as
a black-box that transforms passages into precisely-formatted, structured
summaries of material property data, thus enabling researchers with little NLP
experience to use the toolkit. While PropertyExtractor is currently
implemented for OpenAI gpt and Google gemini, its architecture is deliberately
designed for easy adaptation to incorporate any conversational LLM. This
flexibility is achieved by modularizing the component that interfaces with the
LLM, allowing for simple modifications of a specific subroutine to accommodate
alternative models. Such an adaptable system ensures that PropertyExtractor
not only keeps pace with the rapid advancements in the field of LLMs but also
leverages these improvements to enhance its functionality. The evolving
landscape of LLMs development suggests a future where the continual
improvements in model performance could further amplify the efficacy of
PropertyExtractor. Drawing parallels from the field of image generation, where
prompt engineering has become a standard practice to secure high-quality
results, a similar trend is expected in data extraction. Our approach, with
its foundation in dynamical in-context learning, prompt engineering, and
conversational prompts, positions PropertyExtractor as a versatile tool
adaptable to the forthcoming generations of LLMs, ensuring high-quality data
extraction across diverse applications.

##  I Results and Discussions

###  I.1 Data Extraction Workflow

Figure 1 shows a concise workflow of the integrative unstructured data
collection via API and structured data extraction with the PropertyExtractor.
In Figure 2, we present a detailed workflow illustrating the essential
processes and steps for extracting material properties from unstructured
research papers. The data extraction process begins with data preparation.
This stage involves programmatically gathering relevant scientific literature
using various APIs and refining the content to create clean, unstructured data
suitable for the conversational language model. The data curation is
specifically designed to target texts mentioning the principal material
property and may include an optional set of keywords related to the specific
property, using an extensive set of keywords to cover the diverse terminology
within the field. While the keywords are optional, they are essential for
ensuring that the extracted data is relevant to the specified material
property. For example, extracting energy band gap specific to 2D materials
could have “band gap” as the property and “2D material” as one of the
keywords. The initial process of the data extraction involves two distinct
stages. The first stage is the data collection phase, where scientific papers
are programmatically gathered using API. This is followed by the data
preparation phase, where the collected papers are cleaned to remove XML/HTML
tags and other syntactical clutter and then segmented into individual
sentences for further processing. Following the cleaning of unstructured data,
the next crucial step involves incorporating the LLM-based model, which is
enhanced by dynamic zero-shot-few-shot in-context learning. This advancement
refines the LLM’s conversational interactions with the data using contextually
rich prompts. We found that integrating zero-shot and few-shot in-context
learning with dynamic refinement through feedback on recently, accurately
predicted outcomes enables the LLM to adaptively refine the data extraction
process. This strategy significantly enhances extraction accuracy by
minimizing errors and preventing data hallucinations. It effectively addresses
the challenges posed by the diverse structures, complexity, and terminology
found in unstructured scientific literature, ensuring meticulously calibrated
responses for high-fidelity data extraction. The critical steps of this
process are broken down as follows:

  1. 1.

Initial data classification. We begin with an initial screening using a simple
relevancy prompt. This step is crucial for filtering out sentences that lack
pertinent data about the property of interest.

  2. 2.

Data extraction and validation. This stage involves a sophisticated,
multistage extraction process. Central to this phase is the application of
dynamic zero-shot-few-shot in-context learning. The model not only learns from
a carefully selected array of relevant examples but also incorporates feedback
from three recent accurate predictions. This method enhances the model’s
understanding of complex scientific concepts, significantly improving the
accuracy of data extraction. This approach involves the following (Figure 2):

     * •

Employing engineered prompts. The model utilizes engineered prompts that
facilitate learning from prior examples. This foundational step improves the
model’s capability to parse and accurately extract data about material
properties, setting the stage for more complex interactions.

     * •

Dynamically adjusting prompts. As the model processes the data, it dynamically
adjusts the prompts based on recent analyzes. This adaptation captures the
complexity and variability inherent in scientific texts, tailoring
interactions to improve understanding and response accuracy.

     * •

Handling data variability. The model is equipped with strategies to
efficiently manage both single- and multi-valued data points, enhancing its
adaptability across various data extraction scenarios. For multi-valued
scenarios, the model uses regex patterns and dynamic zero-shot-few-shot in-
context learning to address the complexity of extracting and correctly
associating each value with its respective material and property. This method
begins with detecting the presence of multiple data points within a sentence,
followed by tailored prompts that guide the model in differentiating and
processing these values accurately. Additionally, the model employs prompts
that encourage critical evaluation of its responses. This not only reduces
errors but also significantly enhances the trustworthiness of the extracted
data by ensuring that each data point is accurately captured and attributed.

     * •

Critique and uncertainty quantification. The model can evaluate its own
performance, critiquing its own outputs to explicitly acknowledge when
essential data may be missing from the text. This precaution is designed to
prevent the model from “hallucinating” or generating non-existent data to
fulfill the task requirements. Additionally, to refine its accuracy further,
the model employs uncertainty-inducing redundant prompts that encourage
negative answers when appropriate. This strategy allows the model to
critically reanalyze the text, avoiding the reinforcement of potentially
incorrect previous answers. This iterative reevaluation process is crucial in
minimizing errors and enhancing the trustworthiness of the extracted data.

     * •

Customization through user input. Users can provide optional arguments for
custom prompts and keywords tailored to specific properties being extracted,
such as thickness in the case of 2D materials. Users can also assign weights
to these keywords based on their priority and improve the significance of the
keywords through synonyms, optimizing the model’s focus and relevance to the
targeted extraction task.

     * •

Data extraction and standardization. Enforce rigorous standardization and
structured data entry to ensure uniformity of the property values, enhance
consistency, and facilitate automated data processing.

Figure 2: Flowchart of the PropertyExtractor code for obtaining structured
dataset with a conversational large language model. The flow diagram is made
up several interrelated prompt sections guiding the framework for the
successful and accurate extraction of materials properties in the form of the
quadriplets []material, property value, original unit, method].

While the prompts associated with the data classification task are the first
consequential prompts the model interacts, we have found that setting the
stage by informing the model of the “task description” — explicitly telling
the LLM that the task is to analyze scientific literature and identify certain
properties — increases the predictability of the model. The data extraction
process begins with a critical initial classification step, involving a
preliminary prompt designed to assess the relevance of each sentence within a
scholarly paper. The primary goal at this stage is to determine whether a
sentence contains pertinent information regarding the material property of
interest, such as the property (e.g., thickness), and the corresponding values
and material names. Given the vast amount of content in scientific papers,
even after narrowing the papers through initial keyword searches, the
proportion of sentences containing relevant data is exceedingly low —
typically around $13\%$. Hence, the immediate elimination of irrelevant
sentences — those that do not contain at least the property and its value — is
imperative to enhance efficiency and focus the analysis on potentially useful
data. The LLM-based PropertyExtractor toolkit is designed to process input
texts ranging from as small as an abstract to as large as the entire article,
including tables. After initially classifying the entire text to determine the
presence of relevant material properties, we have found that dynamically
breaking the large texts into smaller chunks, such as paragraphs, improves
efficiency and reduces contextual overload. LLMs often struggle with
processing extremely long sequences of text due to computational limitations.
Operational experience suggests that maintaining the brevity of the text
passage is paramount for achieving the highest accuracy in data extraction.
While it is technically feasible to expand the text passage further to capture
more comprehensive data points, such expansions often do not justify the cost
due to the marginal increase in accuracy and the potential detriment to the
precision of the extraction process. Nevertheless, the methodology for text
selection and the extent of text expansion can be fine-tuned based on the
specific characteristics of different LLMs or the particular properties
targeted in the analysis. Tailoring these parameters may lead to improvements
in data extraction accuracy and efficiency in certain scenarios.

In the data extraction and validation phase following the initial data
classification, we focus on extracting a quadruple of material features:
chemical formula, property value, original unit, and method. While data are
strictly created when the pair comprising the chemical formula of the material
and the property value is present, we foresee broader applications of
PropertyExtractor, such as discerning whether a material’s property value is
derived from computational methods or experimental techniques. This
distinction is crucial for constructing a high-fidelity database. We employ a
combination of task-descriptive instructions and non-prescriptive guidance
(employing engineered prompts) to facilitate dynamic in-context learning
through a self-determined feedback mechanism (dynamically adjusting prompts).
Generic prompts often struggle to manage texts with multiple property values.
We have found that utilizing regex patterns for straightforward cases and
dynamic, context-sensitive prompting for more complex scenarios within the LLM
architecture enables tailored data extraction processes that are both
efficient and reliable for texts containing single or multiple values
(handling data variability). Self-assessment mechanisms are integrated at each
step of the process (critique and uncertainty quantification) to allow the
model to evaluate its own performance and explicitly recognize instances where
essential data may be missing. Through dynamic feedback, the model is equipped
to prevent itself from reinforcing potentially inaccurate prior responses and
to critically reanalyze the text. Iteratively reevaluating the extracted data
is essential to improving reliability. The model critiques its own outputs to
ensure no essential data is omitted and employs uncertainty-inducing redundant
prompts that encourage negative answers when appropriate. This strategy
prevents the model from “hallucinating” or fabricating data to meet task
requirements, critically reanalyzing the text to avoid reinforcing incorrect
previous answers. This iterative reevaluation process is crucial in minimizing
errors and enhancing the trustworthiness of the extracted data.

Furthermore, it is important to recognize that despite the conversational
model’s capability to retain information throughout a dialogue, augmenting the
dialogue with accurately predicted tasks is crucial for preserving detailed
information about the overall nature and complexity of the type of text being
analyzed. As discussions progress, the model may tend to overlook finer
details. Thus, the conversational aspect and the strategy of information
retention significantly enhance the quality of responses and underscore the
benefits of using blended and structured prompts. The ability to retain
crucial information in a conversational context is essential for ensuring both
the accuracy and completeness of the extracted data. The extraction and
standardization of data using LLMs present significant challenges. Although
strict binary “Yes” or “No” responses have been proposed to streamline the
generation of property entries, Polak2024  this approach can restrict the
precision achievable with LLMs. We have developed a more robust approach that
combines the power of regular expressions (regex) with structured responses
for enhanced property extraction. This nuanced strategy leverages the
versatility of regex patterns alongside structured response frameworks,
facilitating the extraction of relevant properties without the limitations
imposed by binary choices. To ensure consistency and support downstream
analysis, we first implement a rigorous standardization protocol. Unit
harmonization: Property values are converted to a standardized unit specified
by the user (e.g., thickness in Å), while original units are retained within
the metadata for reference. This approach helps in reducing potential errors
in data interpretation. Structured entry: Each verified material entry is
systematically compiled into a quadruple format: material [chemical formula],
property value [converted value], unit [original unit], and method [method].
This structured format is efficiently extracted using regex patterns, which
not only maintains the integrity and usability of the information but also
enhances its utility for scientific analysis. By implementing such stringent
protocols, we not only minimize uncertainty but also enhance the efficiency of
data handling and analysis through streamlined automation.

Figure 3: Material property database with PropertyExtractor. A snapshot of the
extracted thickness data for atomically thin 2D materials, illustrating the
range and diversity of the autonomously obtained database.

###  I.2 Performance Evaluation

We evaluated the performance of PropertyExtractor by generating a database for
the thickness of 2D materials. This focus on thickness is driven by two main
factors. First, despite its crucial importance for integrating 2D materials
into devices, there is currently no database or computational framework for
determining the thickness of these materials. The thickness of 2D materials
significantly influences their electronic structure, optical properties,
mechanical behavior, and chemical reactivity. For example, MoS2 exhibits a
transition from an indirect to a direct bandgap when reduced to a single
layer, enhancing its suitability for optoelectronic devices. Similarly, the
mechanical properties of graphene and the surface-to-volume ratio, critical
for catalysis and sensor applications, are thickness-dependent. This property
is also vital for the performance of energy storage devices, impacting ion
transport and storage capacity.

Second, the thickness dataset poses a significant challenge due to the
potential for confusion with similar properties, such as layer count or
interlayer spacing, which require precise differentiation. Hence, it provides
a robust testbed to evaluate the scalability and capability of
PropertyExtractor, demonstrating its effectiveness in accurately discerning
and extracting complex data amidst closely related variables.

Text Mining and Database Generation. The acquisition of thickness information
for 2D materials is challenging due to data scarcity. Despite having access to
APIs, obtaining reliable thickness values from a single source remains
difficult. We utilized several APIs, including Elsevier’s ScienceDirect API,
CrossRef REST API, and PubMed API. API calls were conducted using a
combination of the keywords “Thickness of 2D materials” and variations such as
“Thickness measurement of 2D materials,” “Thickness determination of two-
dimensional materials,” or “Characterization of 2D material thickness.” These
texts were subsequently pre-processed and cleaned to retain only those
containing abstracts or full texts and the keyword “thickness,” resulting in a
collection of 458 full-text articles from the Elsevier’s ScienceDirect API,
424 abstracts from the PubMed API, and 8,387 abstracts from the CrossRef REST
API.

Fulltexts or abstracts were processed using the Google gemini-pro API
conversational language model within Python 3.10.12, employing our dynamic
zero-shot-few-shot in-context learning and prompt engineering approach. This
process yielded 1,221 raw data points, which, after cleaning, resulted in
1,015 data points. Further post-processing standardized these to 584 data
points with units specified in Å. Among these, some records pertained to
materials that might not be fully atomically thin 2D materials, despite
initial keyword searches designed to exclude such instances. The inclusion of
non-2D materials does not reflect a deficiency in the capabilities of our
conversational LLM, as these data were present in the literature sourced.
Restricting the database exclusively to atomically thin 2D materials yielded a
final standardized database containing thickness values for about 43% of the
dataset. The extracted thickness dataset is dominated by the well-known 2D
materials such as graphene, transition metal dichalcogenides, BN, phospherene,
etc.(Figure 3). Within this dataset, 68 thickness values corresponded to
unique materials. It is important to note that in cases where texts explicitly
mention 2D material thickness, the model extracted these instances with nearly
100% accuracy, demonstrating the robustness of PropertyExtractor in handling
texts with less ambiguous keyword descriptions.

Evaluation Methodology for PropertyExtractor. Given the lack of a ground truth
database for the thickness of 2D materials, we developed a unique approach to
evaluate the performance of PropertyExtractor. We curated a dataset from the
scientific literature, extracting data to establish a ground truth. From
approximately 12,000 fulltexts or abstracts, we selected 100 relevant ones
containing thickness data. This selection process was targeted to ensure that
the model only processes potentially useful data, optimizing computational
resources and focusing on relevant texts. We defined our ground truth as 50
manually extracted data points from these texts, focusing on triplets
comprising the material [chemical formula], its thickness value, and the
measurement unit. This methodology allows for a precise evaluation by testing
the model against a well-defined set of data, which is crucial for assessing
the tool’s capability to accurately extract specific material properties from
complex scientific texts. The validation process is carried out using both
gemini-pro and gpt-4.

Figure 4: Performance Evaluation of PropertyExtractor. Confusion matrix
comparing the ground truth with data extracted by PropertyExtractor,
showcasing 45 true positives, 2 false positives, and 3 false negatives, which
are used to calculate the model’s precision, recall, accuracy, and error
metrics.

To design the statistical metrics for evaluating PropertyExtractor, we
generate a confusion matrix (Figure 4. This matrix compares predicted values
to actual target values, providing counts of true positives (TP), true
negatives (TN), false positives (FP), and false negatives (FN), thereby
facilitating a detailed analysis of the model’s accuracy, precision, recall,
and other metrics. The evaluation process is outlined as follows: (1) Ground
Truth and Extracted Data: We define ground truth as the hand-extracted
triplets of material, value, and unit from the text, with the model producing
zero or more extracted triplets. (2) Evaluation Criteria: FP arise when
extracted triplets are present but not in the ground truth; FN occurs when the
ground truth contains triplets but the extracted data does not; TP are noted
when each extracted triplet matches a ground truth triplet in terms of
material, value, and unit. Since our focus is on correct/incorrect labels, TN
is not applicable, implying $\textit{TN}\approx 0$. (3) Comparison of
Triplets: A TP is counted if a matching triplet is found. A FP is counted if a
non-matching triplet is found. Multiple extracted triplets compared to a
single ground truth triplet count as TP for the first correct match, with
subsequent matches counted as FP. For multiple ground truth triplets vs.
extracted data, the absence of extracted triplets results in multiple FN, and
any match with ground truth counts as a TP. (4) Definition of Equivalence:
Extracted triplets must exactly match ground truth in units and values, and
the material names must uniquely identify the same material system.

Evaluation and Accuracy Analysis. The primary statistical metrics employed to
evaluate the performance of PropertyExtractor are precision (P), recall (R),
F1-score (F1s), accuracy (Acc), and the error rate (Er) given as:

P
$\displaystyle=\frac{TP}{TP+FP};\,\text{R}=\frac{TP}{TP+FN};\,\text{F1}_{s}=2\times\frac{P\times
R}{P+R}$ Acc
$\displaystyle=\frac{TP}{TP+FP+FN},\,\text{E}_{r}=\frac{FP+FN}{TP+FP+FN}.$

Utilizing PropertyExtractor with gemini-pro, the metrics achieved are
precision of 95.74%, recall of 93.75%, F1-score of 94.73%, accuracy of 90.00%,
and an error rate of approximately 10.00%. These values indicate that
PropertyExtractor correctly predicts a triplet 95.56% of the time (precision)
and successfully identifies 93.48% of all relevant triplets (recall). The
accuracy of 89.58% reflects the overall correctness of the tool, accounting
for both positives and negatives. An F1-score of approximately 94.51% suggests
a balanced model in terms of precision and recall. The error rate, at around
10.42%, demonstrates the model’s effectiveness, with a small proportion of the
predictions being incorrect. Furthermore, when evaluations are specifically
based on the material and standardized thickness values, the performance
notably improves, exemplified by a precision of approximately 98%. We note
that the accuracy using gpt-4 is similar to that obtained with gemini-pro, but
gpt-4 performs better in the effective determination of the method used and
also in discerning data that are provided as a range.

##  II Conclusions

This paper demonstrates the power of zero-shot-few-shot in-context dynamical
learning when integrated within conversational LLMs such as Google gemini-pro
and OpenAI gpt-4 as implemented in the open-source toolkit, PropertyExtractor.
PropertyExtractor provides an easy to use computational architecture to
achieve accurate, scalable, and transferable material property data
extraction, enabling the creation of high-fidelity databases for use with
downstream applications and models such as machine learning applications and
the construction of knowledge graphs. We demonstrate the effectiveness of
PropertyExtractor by generating a unique database of thickness of 2D
materials, achieving impressive accuracy metrics: precision above 95%, recall
of $\sim$93%, accuracy of $\sim$90%, F1-score of $\sim$95%, and an error rate
of only $\sim$10%. This database addresses a critical gap in materials science
for 2D-based materials where thickness information is crucial to harnessing
the intrinsic thickness-dependent features of 2D materials. The adaptability
of PropertyExtractor and its model independence ensure it can evolve alongside
advancements in LLMs architecture. As newer and more advanced LLMs come into
existence, the efficacy and applicability of PropertyExtractor are poised to
broaden, providing unprecedented opportunities for sophisticated data
extraction across diverse scientific fields.

##  III Method

PropertyExtractor is a conversational large language model toolkit designed
for extracting physical properties from scientific articles. It incorporates a
dynamic zero-shot-few-shot in-context learning architecture. Although
PropertyExtractor is highly adaptable and can utilize various LLM models, it
is currently optimized for use with Google Gemini Pro and OpenAI GPT-4.
PropertyExtractor is designed to leverage the latest Python libraries;
specifically, we used Python 3.10.12.

Installation. The preferred installation method is via pip, the Python package
manager, which simplifies the installation process. To install, execute the
command: pip install -U propertyextract. Alternative traditional methods, such
as downloading the sources and manual installation, are also available. Once
installed, the essential input files required for setting up property
extraction from unstructured scientific papers can be generated by running the
command propextract -0. This command produces the main PropertyExtractor input
file, extract.in, as described in Table 1, along with two optional files:
keywords.json and additionalprompt.txt. These files offer further
customization options for both the keywords specific to the property being
extracted and the additional custom prompts, respectively. The essential
parameters necessary for successfully running the model configuration used in
this paper are presented in Table 1 and detailed below.

  * •

model_type: Type of the model used (gemini/chatgpt).

  * •

model_name: Specific name of the model (gemini-pro/gpt-4).

  * •

property_name: The physical property being extracted (e.g., thickness).

  * •

property_unit: Harmonized unit for the physical property (e.g., angstrom).

  * •

temperature: The temperature condition under which the model operates, in
degrees Celsius (default is “0.0”).

  * •

top_p: The probability threshold for the model’s output generation (e.g.,
0.95).

  * •

max_output_tokens: Maximum number of output tokens generated by the model
(e.g., 80).

  * •

use_keywords: Toggle to determine whether keywords should be utilized in
processing (True/False).

  * •

additional_prompts: File containing additional prompts that can be used to
guide the model (e.g., additionalprompt.txt).

  * •

inputfile_name: Name of the CSV file containing the input data.

  * •

column_name: The specific column in the input file to be used for data
extraction (e.g., Text).

  * •

outputfile_name: Name of the file where the processed output data will be
saved (e.g., output.csv).

Table 1: The control parameters and the representative values used in the PropertyExtractor code.  Parameters | Values
---|---
model_type | gemini/chatgpt
model_name | gemini-pro/gpt-4
property_name | thickness
property_unit | angstrom
temperature | 0.0
top_p | 0.95
max_output_tokens | 80
use_keywords | True
additional_prompts | additionalprompt.txt
inputfile_name | thickness.csv
column_name | Thickness
outputfile_name | processed.csv

##  IV Acknowledgments

This work was supported by the U.S. Department of Energy, Office of Science,
Basic Energy Sciences under Award DE-SC0024099. Computational support is
provided by Computational materials group at Lehigh University.

## Data Availability

The extracted database of thickness of 2D-based materials is available
atPropertyExtractor@github and via Zenodo at 10.5281/zenodo.11205500. The
thickness database developed as part of this software is included in the code
website.

## Code Availability

The code, PropertyExtractor, developed in this paper is available at GitHub:
PropertyExtractor@github and via Zenodo at 10.5281/zenodo.11205500. The code
repository includes an easy-to-follow readme and a folder containing the data
used in validating the performance. Additionally, the repository provides
detailed instructions on setting up and using PropertyExtractor, ensuring that
users can replicate the results presented in this paper and apply the tool to
their own datasets.

## References

  * (1) O. Kononova, T. He, H. Huo, A. Trewartha, E. A. Olivetti, G. Ceder, Opportunities and challenges of text mining in materials research.  iScience 24, 102155 (2021).
  * (2) L. P. J. Gilligan, M. Cobelli, V. Taufour, S. Sanvito, A rule-free workflow for the automated generation of databases from scientific literature.  npj Computational Materials 9, 222 (2023).
  * (3) M. P. Polak, D. Morgan, Extracting accurate materials data from research papers with conversational language models and prompt engineering.  Nature Communications 15, 1569 (2024).
  * (4) K. M. Jablonka, et al., 14 examples of how llms can transform materials science and chemistry: a reflection on a large language model hackathon.  Digital Discovery 2, 1233-1250 (2023).
  * (5) J. Dagdelen, A. Dunn, S. Lee, N. Walker, A. S. Rosen, G. Ceder, K. A. Persson, A. Jain, Structured information extraction from scientific text with large language models.  Nature Communications 15, 1418 (2024).
  * (6) N. Walker, S. Lee, J. Dagdelen, K. Cruse, S. Gleason, A. Dunn, G. Ceder, A. P. Alivisatos, K. A. Persson, A. Jain, Extracting structured seed-mediated gold nanorod growth procedures from scientific text with llms.  Digital Discovery 2, 1768-1782 (2023).
  * (7) S. Huang, J. M. Cole, Batterybert: A pretrained language model for battery database enhancement.  Journal of Chemical Information and Modeling 62, 6365-6377 (2022). PMID: 35533012.
  * (8) Z. Zheng, O. Zhang, C. Borgs, J. T. Chayes, O. M. Yaghi, Chatgpt chemistry assistant for text mining and the prediction of mof synthesis.  Journal of the American Chemical Society 145, 18048-18062 (2023). PMID: 37548379.
  * (9) C. M. Castro Nascimento, A. S. Pimentel, Do large language models understand chemistry? a conversation with chatgpt.  Journal of Chemical Information and Modeling 63, 1649-1655 (2023). PMID: 36926868.
  * (10) T. Xie, Y. Wan, W. Huang, Z. Yin, Y. Liu, S. Wang, Q. Linghu, C. Kit, C. Grazian, W. Zhang, I. Razzak, B. Hoex, Darwin series: Domain specific large language models for natural science.  arXiv preprint arXiv:2308.13565 (2023). ArXiv:2308.13565v1 [cs.CL].
  * (11) Q. Dong, L. Li, D. Dai, C. Zheng, Z. Wu, B. Chang, X. Sun, J. Xu, L. Li, Z. Sui, A survey on in-context learning.  arXiv preprint arXiv:2301.00234 (2023).
  * (12) K. S. Novoselov, V. I. Fal$\prime$ko, L. Colombo, P. R. Gellert, M. G. Schwab, K. Kim, A roadmap for graphene.  Nature 490, 192–200 (2012).
  * (13) S. Kastuar, C. Ekuma, Z.-L. Liu, Efficient prediction of temperature-dependent elastic and mechanical properties of 2d materials.  Scientific Reports 12, 3776 (2022).
  * (14) S. Najmaei, C. E. Ekuma, A. A. Wilson, A. C. Leff, M. Dubey, Dynamically reconfigurable electronic and phononic properties in intercalated hfs2.  Materials Today 39, 110-117 (2020).
  * (15) S. Khanmohammadi, K. Kushnir Friedman, E. Chen, S. M. Kastuar, C. E. Ekuma, K. J. Koski, L. V. Titova, Tailoring ultrafast near-band gap photoconductive response in ges by zero-valent cu intercalation.  ACS Applied Materials & Interfaces (2024).


Stoner]Cynthia Stoner
For graphs $G$ and $H$, what relations can be determined between $t(G,W)$ and $t(H,W)$ for a general graph $W$? We study this problem through the framework of the density domination exponent, which is defined to be the smallest constant $c$ such that $t(G,W)\ge t(H,W)^c$ for every graph $W$. This broad generalization encompasses the Sidorenko conjecture, the Erdős-Simonovits Theorem on paths, and a variety of other statements relating graph homomorphism densities. We introduce some general tools for estimating the density domination exponent, and extend previous results to new graph regimes.

§ INTRODUCTION

Given the density of one graph $G$ in a target graph(on) $W$, what can we say about the density of another graph $H$? Many problems in extremal graph theory fit into this framework. In order to discuss these, we first introduce some basic definitions.

Given two graphs $G,W$, a graph homomorphism is a vertex map $\phi:V(G)\to V(W)$ such that, for every edge $(u, v)$ in $G$, the image $(\phi(u), \phi(v))$ is an edge in $W$. The number of such maps is denoted by $\hom(G,W)$.

For example, when $G=W=K_n$, every homomorphism $\phi: V(G)\to V(W)$ corresponds to a permutation of the vertices of the complete graph $K_n$, so $\hom(G,W)=n!$.

For graphs $G$ and graphons $W$, define the graph density or graphon density $t(G,W)$ as follows.

If $W$ is a graph, then

\[t(G,W)=\frac{\hom(G,W)}{|V(W)|^{|V(G)|}}.\]

If $W$ is a graphon, and the vertices of $G$ are labeled $v_1,\ldots, v_n$, $n=|V(G)|$, then

\[t(G,W)=\int_{[0,1]^{n}}\prod_{(v_i, v_j)\in E(G)}W(x_i,x_j)\prod_{i=1}^ndx_i.\]

In the case that $W$ is a graph, $t(G,W)$ denotes the probability that a random map of vertices $V(G)\to V(W)$ is a homomorphism. We will sometimes replace $G$ with the graph itself for visual purposes; for instance, $t(\edge, W)=t(K_2,W).$

Sidorenko's conjecture, which states that $t(H,W)\ge t(\edge, W)^{|E(H)|}$ for bipartite graphs $H$, has been the object of much interest in recent decades (for example, [8], [11]). It states that, for all graph(ons) $W$, and bipartite graphs $H$, the inequality $t(H,W)\ge t(\edge, W)^{|E(H)|}$ holds. In other words, for any fixed bipartite $H$ and edge density $d\in (0,1)$, the homomorphism density of $H$ in $W$ is minimized when $W$ is the uniform graphon $W:=d$ (or in the graph case, a large pseudorandom graph $G(N,d)$).

In this work, we examine a more general framework, which was introduced by Blekherman and Patel in [2], who dealt with the case when the target graph is a single edge. The main object of study will be the following metric, which is the density analogue of the homomorphism domination exponent studied in [10].

Given two simple graphs $G,H$, the density domination exponent $\rho(G,H)$ is defined as follows:

\[\rho(G,H)=\sup_W\frac{\log t(H,W)}{\log t(G,W)}\]

where the supremum ranges across graphs or graphons $W$ with $t(G, W)\neq 0$.

A lower bound $\rho(G,H)\ge c$ corresponds to a construction of some graph or sequence of graphs $W_i$ for which $\frac{\log t(H,W_i)}{\log t(G,W_i)}\to c$. An upper bound $\rho(G,H)\le c$ corresponds to a proof that $t(H,W)\ge t(G,W)^c$ for every graph $W$. Proving an equality $\rho(G,H)=c$, therefore, requires both citing a construction and proving the corresponding bound. Since they are equivalent, we will use the graph and graphon formulations of Definition <ref> interchangeably.

Using the $\rho$ notation, Sidorenko's conjecture becomes $\rho(\edge, H)=E(H)$ for bipartite graphs $H$. Indeed, the statement itself is directly equivalent with $\rho(\edge, H)\le E(H)$, and $\rho(\edge, H)\ge E(H)$ follows from taking $W$ to be the constant $\frac{1}{2}$ graphon.

The question of the relative densities of graphs and their blowups [12] or the $3$-uniform triforce hypergraph and hyperedge [4] also fit into this general framework. The former, for instance, studies the value $\rho(K_{1,1,1}, K_{a,b,c})$ for some regimes of positive integers $a,b,c$.

In Section 2, we introduce some fundamental properties of $\rho(\cdot, \cdot)$, and provide useful methods for proving the upper-bound inequalities (i.e., those of the form $\rho(H,G)\ge c$, which is equivalent to $t(H,W)\ge t(G,W)^c$ for all $W$.) We also give some constructions which will be useful for verifying the corresponding lower bounds.

In Section 3, we discuss the special case $H=K_{1,t}$, where we can give exact answers in some regimes and one-sided bounds in the rest. Sections 4 and 5 also follow this structure. Section 4 studies the case where both $G$ and $H$ are paths or cycles, and finds exact bounds for all but a few regimes, and Section 5 does the same for complete and complete multipartite graphs. One particular example of interest is the case where $G,H$ are both paths. This case encapsulates both the Blakely-Roy inequality and the Erdős-Simonovits Theorem. In Theorem <ref>, we establish the value $\rho(P_m,P_n)$ in all cases except when $m>n$ are odd with $n+1\not| m+1$.

Finally, in Section 6, we discuss some of the remaining open questions, including some minimum unresolved cases from the previous sections.

In addition to the methods developed in Section 2, we also employ a wide variety of other techniques and constructions to establish $\rho$ values in particular regimes. For instance, in Lemma <ref>, a weighted form of Shearer's entropy lemma is used on a certain generalization of bipartite graphs, while in the proof of Theorem <ref> we develop a fractional form of the Blakely-Roy inequality. In Theorem <ref>, we use a construction of Gowers and Janzer, along with some double counting, an alternate characterization of vector majorization proved in Lemma <ref>, and Proposition <ref> to prove a result about the density domination exponent of complete multipartite graphs.

Throughout, we will use the convention that $d_S=|\bigcap_{v\in S}N(v)|$, where $S\subset V(W)$ is a nonempty collection of vertices in $W$.

§ BASIC PROPERTIES

We state the following proposition without proof, as these facts follow directly from the definition of $\rho$.

The following hold for all graphs $G,H,J$ and positive integers $n$. Here, $nG$ denotes the union of $n$ disjoint copies of $G$.

* $\rho(G,H')\ge \rho(G,H)\ge \rho(G', H)$ and $\rho(G,G')\ge 1$ for any subgraphs $H'\subset H, G'\subset G$.

* $\rho(G,H)\rho(H,J)\ge \rho(G,J)$.

* $\rho(nG,H)=n\rho(G,H)$.

* $\rho(G,nH)=\frac{1}{n}\rho(G,H)$.

In addition to these, our primary basic tool for the bound proofs will be the following consequence of Holder's inequality. Given a graph $G$ and extra disjoint graphs $S_1, \ldots, S_n$ which are connected to $G$ in a specified way and a nonnegative integer vector $\textbf{k}=\{k_1,\ldots, k_n\}$, let $G_{\{S_i\}}(\bf k)$ denote the graph obtained by, for each $i$, copying the graph $S_i$, $k_i$ times, and attaching each copy to $G$ in the same way that $S_i$ is attached.

For a nonnegative integer vectors $\bf x, \bf y, \bf z$ and positive integers $a,b,c$ such that $a\textbf{x}+b\textbf{y}=(a+b)\bf z$, it holds for any graph $G$, disjoint graphs $\{S_1,\ldots, S_n\}$ with implicit connections to $G$, and graphon $W$ that

\[t(G_{\{S_i\}}(\bf x),W)^{a}t(G_{\{S_i\}}(\bf y),W)^{b}\ge t(G_{\{S_i\}}(\bf z),W)^{a+b}.\]

Via the definition of graph density, we may compute

\begin{gather*}t(G_{\{S_i\}}(\bf x),W)= \\\int_{[0,1]^{|V(G)|}}\prod_{(v_i, v_j)\in E(G)} W(v_i, v_j)\prod_{\ell=1}^n(\int_{[0,1]^{|V(S_\ell)|}}\prod_{(v_i,v_j)\in E(G\cup S_\ell)\sm E(G)}W(v_i, v_j)\prod_{v_i\in V(S_\ell)}dv_i)^{x_\ell}\prod_{v_i\in V(G)}dv_i\end{gather*}

The product over $\ell$ is a nonnegative measurable function of the $v_i\in V(G)$. The result therefore follows from an application of Holder's inequality.

Now, we establish a useful existence criterion for $\rho(G,H)$. For this, we first prove the finiteness of this quantity when $H$ is a blowup of $G$.

For a simple graph $G=(V,E), V=\{v_1,\ldots, v_n\}$ and a sequence of positive integers $B=\{b_1,\ldots, b_n\}$, the blowup $B(G)$ is the graph $(V', E')$, where:

* $V'=\{v_{ij}, 1\le i\le n, 1\le j\le b_i\}$.

* $B(G)$ has an edge between $v_{ij}$ and $v_{k\ell}$ if and only if $(v_i, v_k)\in E$.

Let $B=\{b_1,\ldots, b_n\}$ be a sequence of positive integers, and let $G$ be a graph. Then $\rho(G,B(G))\le\prod_{i=1}^nb_i$.

It suffices to consider the case where only one vertex is blown up, since iterating this $n$ times will yield the desired inequality. Hence, assume $b_1=k>1, b_2=\ldots=b_n=1$. Let $G'$ denote the graph obtained by removing $v_1$ from $G$. Then, Proposition <ref> yields, for any graphon $W$:

\[t(G,W)^k\le t(G',W)^{k-1}t(B(G),W)\le t(B(G),W).\]

Hence $\rho(G, B(G))\le k$ as desired.

Now we can show the following.

If $G$ is nonempty, then the density domination exponent $\rho(G,H)$ is finite exactly when $\hom(H,G)>0$.

First, suppose $\hom(H,G)$ is positive. Then $H$ is a subgraph of some blowup $B(G)$ of $G$; from which it follows that $\rho(G,H)\le \rho(G,B(G))$ is finite from the previous proposition.

Now, suppose $\hom(H,G)=0$. Then, take $W\to G$ as a certificate that $\rho(G,H)$ is infinite. We're done.

Finally, we establish several lower bounds which will be useful for the rest of the paper.

The following hold for any nonempty graphs $G,H$.

* $\rho(G,H)\ge \frac{|E(H)|}{|E(G)|}$.

* $\rho(G,H)\ge \frac{|V(H)|}{|V(G)|}$.

* $\rho(G,H)\ge \frac{|V(H)|-1}{|V(G)|-1}$ if $G,H$ are connected.

* $\rho(G,H)\ge \frac{|V(H)|-\alpha(H)}{|V(G)|-\alpha(G)}$, where $\alpha(G)$ is the independence number of $G$.

We exhibit the four constructions which correspond to these lower bounds.

* Take $W$ to be the constant graphon, $W=p, 0<p<1$. Then $t(G,W)=p^{|E(G)|}$, while $t(H,W)=p^{|E(H)|}$, yielding the desired ratio.

* Take $W$ to be the graphon for which $W(x,y)=1$ if $x<\frac{1}{2}$ and $y<\frac{1}{2}$, and $W(x,y)=0$ otherwise. Then $t(G,W)=2^{-|V(G)|}$, while $t(H,W)=2^{-|V(H)|}$, yielding the desired ratio.

* Take $W$ to be the graphon for which $W(x,y)=1$ if $x, y<\frac{1}{2}$ or $x, y>\frac{1}{2}$, and $W(x,y)=0$ otherwise. Then $t(G,W)=2^{1-|V(G)|}$, while $t(H,W)=2^{1-|V(H)|}$, yielding the desired ratio.

* Take $W_i$ to be the graph corresponding to $K_{1,i}$ with a loop on the distinguished vertex, and consider the sequence $\{W_i\}.$ Then $t(G,W_n)=n^{\alpha(G)-|V(G)|+o(1)}$, while $t(H,W)=n^{\alpha(G)-|V(H)|+o(1)}$, yielding the desired ratio.

We'll give an example which demonstrates these tools in use, and also shows that the four constructions in the previous proposition do not provide tight bounds for all pairs $(G,H)$.

For $G=\ptri$ and $H=\squ$, it holds that $\rho(G,H)=\frac{4}{3}$.

All of the constructions in Proposition <ref> yield a lower bound on $\rho(G,H)$ of $1$. We can improve this by considering the graphon equivalent to the following weighted, looped graph on $n$ vertices for large $n$. Let $n-1$ vertices have uniform edge and loop weight $\frac{1}{\sqrt{n}}$, and let the last vertex have a weight $1$ loop and be connected to all other vertices with edge weight $1$.  Taking $W$ to be the corresponding graphon, we find that $t(G,W)=\Theta(n^{\frac{3}{2}})$, while $t(H,W)=\Theta(n^2)$. Taking $n\to\infty$, this family of graphons shows that $\rho(G,H)\ge\frac{4}{3}$.

Now we prove the upper bound. For this, we use the following chain of inequalities, valid for any graphon $W$:

\begin{align*}
t(G,W)^2&=t(\ptri, W)^2
\\ &\le t(\ptria, W)t(\ptrib, W)
\\ &\le t(\ptric, W)t(\ptrib, W)
\\ &\le t(\squ, W)t(\squ, W)^{\frac{1}{2}}
\\ &= t(H, W)^{\frac{3}{2}},
\end{align*}

which rearranges to $t(H, W)\ge t(G, W)^{\frac{4}{3}}$ as required. Here, the first inequality is due to Proposition <ref>, the second follows from a subgraph property, and the last inequality is two applications of the Cauchy-Schwarz inequality.

§ $H$ IS A STAR

In [1], Alon found tight bound for the extremal values of the asymptotic log-ratio of the number of copies of a graph $H$ in a larger graph $G$, and the number of edges of $G$. We use some of these methods to prove an analogous result for the density domination exponent when $H=\edge$, and extend one direction of this inequality to the case $H=K_{1,t}$.

First, we note the following, which is a consequence of Theorem 4 from [13].

Let $G$ be a connected graph with $|V(G)|\le t+1$. Then $\rho(G, K_{1,t})=\frac{t}{|V(G)|-1}$.

From Proposition <ref> part (c), it follows that $\rho(G, K_{1,t})\ge\frac{t}{|V(G)|-1}$. For the other direction, consider any spanning tree $T$ of $G$ and any graphon $W$. We have $t(T,W)\le t(K_{1,|V(G)|-1}, W)$ by the aforementioned theorem, and $t(K_{1,|V(G)|-1}, W)\le t(K_{1,t},W)^{\frac{t}{|V(G)|-1}}$ by Holder's inequality. Hence

\[\rho(G,K_{1,t})\le \rho(T,K_{1,t})\le \frac{t}{|V(G)|-1}\]

and we're done.

For the regime where $G$ as more vertices than $H=K_{1,t}$, we first define the following extension of the delta function introduced in [1].

For a graph $G$ and positive integer $i$, let $\delta_i(G)=\max_S(|S|-i|N(S)|)$, where $S$ ranges across all subsets of $V(G)$.

For all positive integers $t$ and graphs $G$ with $|V(G)|\ge t+1$

\[\rho(G, K_{1,t})\ge \frac{t+1}{|V(G)|-\delta_t(G)}\]

and equality holds when $t=1$.

We handle first the general lower bound. For each positive integer $i$, take $W$ to be the weighted graph defined as follows.

Take a clique of size $\left\lfloor n^{\frac{t}{t+1}}\right\rfloor$ and connect one of its vertices to $n$ additional vertices. Then $t(K_{1,t},W)$ is $\Theta(n)$, while $t(G,W)=\Theta(n^{\frac{t+1}{|V(G)|-\delta_t(G)}})$; hence, this gives the desired lower bound.

Next, we show that equality in fact holds when $t=1$. For this, we use the following two lemmas from [1].

Let $H$ be any graph with $\delta_1(G)=0$. Then $H$ can be vertex-partitioned into edges and odd cycles.

For any graph $G$, there exists an independent set $I$ with $|I|-|N(I)|=\delta_1(G)$.

Now, take any graph $G$, and let $I$ be an independent set chosen such that $|I|-|N(I)|=\delta_1(G)$. Let $H$ be the subgraph of $G$ obtained by removing $I, N(I)$ from $G$. We first claim that $\delta_1(H)=0$. Indeed, suppose otherwise, and let $S\subset V(H)$ be a subset of vertices with $|S|>|N(S)|$. Then

\[|I\cup T|-|N(I\cup T)|=|I|+|T|-N(I)-N_H(T)>\delta_1(G),\]

a contradiction to the definition of $\delta_1$.

Now, let $J$ denote the subgraph of $G$ defined by removing $H$, so that $J\cup H$ is a subgraph of $G$. We claim that every vertex in $N(I)$ can be matched to a unique vertex in $I$, so that the resulting edges are disjoint. Indeed, for this we need only check the Hall's Marriage lemma condition, that for any subset $R\subset N(I)$, we have $|N_J(R)|\ge |R|$. Suppose otherwise, that some $R$ satisfies the opposite inequality. Then

\begin{align*}|I\sm N_J(R)|-|N(I\sm N_J(R))|&= |I|-|N_J(R)|-|N(I)|+2(|N(I)\sm N(I\sm N_J(R))|)
\\ &\ge \delta_1(G)+|R|-|N_J(R)|
\\ &>\delta_1(G),
\end{align*}

once again a contradiction. Therefore such a matching indeed exists, and it follows that:

\[\rho(G, \edge)\le \frac{1}{\frac{|V(H)|}{2}+|J|}=\frac{2}{|V(G)|+|J|-|I|}=\frac{2}{|V(G)|-\delta_1(G)}\]

as desired.

§ PATHS AND CYCLES

In this section, we take $P_n$ to be the path on $n$ edges, and $C_n$ to be the cycle on $n$ edges.

Let $m, n$ be positive integers. Then

\[\rho(P_m, P_n)=\begin{cases}
\frac{n}{m} & n>m,\text{ } n\even
\\ \frac{n}{m} & n>m, n\odd,\text{ } m\odd
\\ \frac{n+1}{m} & n \odd,\text{ } m\even
\\ \frac{n+1}{m+1} & n<m,\text{ } n\even
\\ \frac{n+1}{m+1}, & n<m, n\odd,\text{ } m\odd, n+1|m+1.
\end{cases}\]

The lower bounds all follow from the constructions in Proposition <ref>. In particular, the first and second follow from (a), the third follows from (d), and the fourth and fifth follow from (b).

Now we turn our attention to the upper bounds. The second case, which is the Erdős-Simonovits conjecture, was proved recently by Blekherman and Raymond in [3], where they also discuss the older first case. Together, these cases extend the Blakely-Roy inequality $t(P_m)\ge t(P_1)^m$.

Now we examine the third case. If $n\ge m-1$, then it follows from the inequality chain

\[t(P_n, W)\ge t(P_{n+1}, W)\ge t(P_m)^{\frac{n+1}{m}},\]

where the second inequality follows from the Erdős-Simonovits conjecture. If $n<m-1$, consider an even number $N>m$ such that $n+1|N+1$. Then $P_N$ contains $\frac{N+1}{n}$ vertex-disjoint copies of $P_n$, so $t(P_n, W)\ge t(P_N, W)^\frac{n+1}{N+1}$ for any graphon $W$. So, using the $n\ge m-1$ case,

\[t(P_n, W)\ge t(P_N, W)^\frac{n+1}{N+1}\ge t(P_m, W)^\frac{n+1}{m}\]

as desired.

For the fourth case, we first prove a lemma:

Suppose $a,b,x,y,z$ are positive integers such that $x, y$ are even and $ax+by=(a+b)z$ and let $W$ be any graph. Then

\[t(P_x,W)^at(P_y, W)^b\ge t(P_z, W)^{a+b}.\]

First, consider the special case $y=x+2, z=x+4, a=b=1$. In this case, the inequality becomes $t(P_x, W)t(P_{x+4}, W)\ge t(P_{x+2}, W)^2$, which is a special case of Proposition <ref>. It follows that the sequence

\[\left\{\frac{t(P_4, W)}{t(P_2, W)}, \frac{t(P_6, W)}{t(P_4, W)}, \frac{t(P_8, W)}{t(P_6, W)}, \ldots\right\}\]

is nondecreasing. Therefore, when $y$ is even, and without loss of generality $x<y<z$, we may apply the following inequality chain.

\begin{align*}
(\frac{t(P_y,W)}{t(P_x,W)})^a &\le (\frac{t(P_y,W)}{t(P_{y-2},W)})^\frac{a(y-x)}{2}
\\ &=(\frac{t(P_y,W)}{t(P_{y-2},W)})^\frac{b(z-y)}{2}
\\ &\le (\frac{t(P_{y+2},W)}{t(P_y,W)})^\frac{b(z-y)}{2}
\\ &\le (\frac{t(P_z,W)}{t(P_y,W)})^a
\end{align*}

which rearranges to the desired result. When $y$ is odd, we may use $t(P_y, W)^2\le t(P_{y-1},W)t(P_{y+1}, W)$ to reduce to the even case, so the lemma is proved.

Now we use this lemma. Note that $P_{2mn+2m+n}=P_{(2m+1)(n+1)-1}$ contains $2m+1$ vertex-disjoint copies of $P_n$.

\begin{align*}
t(P_n, W)^{2m(m+1)}&=t(P_n, W)^{(m-n)(2m+1)}t(P_n, W)^{2mn+2m+n}
\\ &\ge t(P_{2mn+2m+n}, W)^{m-n}t(P_n, W)^{2mn+m+n}
\\ &\ge t(P_m, W)^{2m(n+1)}
\end{align*}

as desired.

Finally, the fifth upper bound follows from the fact that $P_m$ contains $\frac{m+1}{n+1}$ copies of $P_n$ when $n+1|m+1$. We're done.

The remaining case, $\rho(P_m, P_n)$ for $n<m$ both odd and $n+1\nmid m+1$, will require a different kind of construction. For example, $\rho(P_5, P_3)\ge \frac{7}{10}$ via the construction in [10] beats the $\frac{n+1}{m+1}$ bound.

For positive integers $m, n$ such that $m>2n$, we have $\rho(C_m, C_{2n})=\frac{2n}{m}$.

The lower bound follows from the construction in Proposition <ref>(a).

For the upper bound, let $W$ be any graph, and let its adjacency matrix be $M$. Suppose the eigenvalues of $M$ are $\lam_1, \ldots, \lam_k$; they are all real because $M$ is nonnegative real symmetric. Then the desired inequality is equivalent with:

\[(\sum_{i=1}^k(\frac{\lam_i}{k})^m)^{\frac{n}{m}}\ge \sum_{i=1}^k (\frac{\lam_i}{k})^n\]

which follows from the monotonocity of the $L_p$ norm. Here, we have used the fact that $\sum_{i=1}^k \lam_i^k$ is the trace of $M^k$, which counts the number of length $k$ cycles in $W$.

Let $m, n$ be positive integers. Then if $m>2$,

\[\rho(C_m, P_n)=\begin{cases}\frac{n+1}{m} & n\le m-1
\\ \frac{n}{m-1} & n\ge m-1
\end{cases}\]

and if $n>1$,

\[\rho(P_m, C_{2n})=\frac{2n}{m}.\]

The lower bounds follows from (b), (c), and (a) respectively in Proposition <ref>, so we turn to the upper bounds.

We'll deal first with the second upper bound. Here, we have the following inequality chain:

\[t(C_{2n}, W)\ge t(C_{2mn}, W)^{\frac{1}{m}}\ge t(P_m, W)^{\frac{2n}{m}}.\]

The first inequality follows from Proposition <ref>, while the second holds since Sidorenko's conjecture is true for cycles.

Now we consider the first upper bound. Suppose that $n\ge m-1$. If $n$ is even, then Proposition <ref> yields the chain:

\[t(P_n, W)\ge t(P_{m-1}, W)^{\frac{n}{m-1}}\ge t(C_m, W)^{\frac{n}{m-1}}\]

since $P_{m-1}$ is a subgraph of $C_m$. If $n$ is odd, then there are two cases. If $m$ is even, then $m-1$ is odd and the proof follows as above. Otherwise, let $C_m'$ denote the graph obtained from making blowing up one vertex in $C_m$ by a factor of two; note that it contains $P_m$ as a subgraph. Then we have the following chain.

\begin{align*}
t(P_n, W)^{2m-2}&= t(P_n,W)^mt(P_n,W)^{m-2}
\\ &\ge t(P_m,W)^nt(P_{m-2},W)^n
\\ &\ge t(C_m', W)^nt(P_{m-2}, W)^n
\\ &\ge t(C_m, W)^{2n}
\end{align*}

where the last line is a special case of Proposition <ref>.

Finally, we give some bounds on $\rho(C_k, C_n)$ for $n$ even, and also for $k<n$ both odd.

Let $n,k$ be positive integers with $2n\ge k\ge 3$. Then

\[\frac{2n-1}{k-1}\le \rho(C_k,C_{2n})\le \frac{2n-1-\frac{1}{2n-1}}{k-1-\frac{1}{2n-1}}<\frac{2n-1}{k-1}+\frac{1}{(k-1)^2}.\]

The lower bound follows from Proposition <ref>(c).

For the upper bound, we use the same setup and notation as in the proof of Proposition <ref>. We calculate, via Holder's inequality:

\begin{align*}
t(C_{2n},W)^{2nk-2n-k}&\ge t(C_{2n},W)^{2n(k-2)}t(K_2,W)^{2n(2n-k)}
\\ &=(\sum_{i=1}^k(\frac{\lam_i}{k})^{2n})^{2n(k-2)}(\sum_{i=1}^k(\frac{\lam_i}{k})^{2})^{2n(2n-k)}
\\ &\ge (\sum_{i=1}^k(\frac{\lam_i}{k})^{k})^{2n(2n-2)}
\\ &= t(C_k, W)^{2n(2n-2)}.
\end{align*}

Therefore $\rho(C_{2n}, C_k)\le \frac{2n(2n-2)}{2nk-2n-k}=\frac{2n-1-\frac{1}{2n-1}}{k-1-\frac{1}{2n-1}}$ as desired.

For fixed $k$ and $n\to\infty$, the difference between lower and upper bounds approaches $\frac{1}{(k-1)^2}$; it would be interesting to close this gap.

Is it true, for positive integers $n,k$ satisfying $2n\ge k\ge 3$, that $\rho(C_k, C_{2n})=\frac{2n-1}{k-1}+o_{k,n}(1)$?

Finally, we consider the case where $n>k$ and both are odd.

Let $n>k$ be positive integers. Then

\[\frac{n}{k}\le \rho(C_{2k+1},C_{2n+1})\le \left\lceil\frac{n}{k}\right\rceil +1.\]

The lower bound again follows from construction (c) in Proposition <ref>.

For the upper bound, we make use of the following to lemmas. For nonnegative reals $0\le \alpha, \beta \le 1$ and a nonnegative integer $r$, define the generalized path $P_{\alpha,r,\beta}$ to be a symbol which satisfies, for graphs $W$,

\[t(P_{\alpha,r,\beta},W)=\frac{1}{|V(W)|^{r+1+\alpha+\beta}}\sum_{v_0, \ldots, v_n\in V(W)\atop (v_i, v_{i+1})\in E(W)\forall i}d_{v_0}^\alpha d_{v_1}^\beta.\]

This can be thought of as a path with partial edges attached at each end, with weights $\alpha$ and $\beta$.

For positive integers $r$, positive reals $0\le \beta\le 1$, and weighted graphs $W$, the following holds.

\[t(P_{0,n,\beta}, W)\ge t(P_1, W)^{n+\beta}.\]

We proceed by induction on $n$. For $n=1$, we may calculate:

\begin{align*}
t(P_{0,1,\beta},W)&= \frac{1}{|V(W)|^{2+\beta}}\sum_{v\in V(W)}d_v^{1+\beta}
\\ &= \frac{1}{|V(W)|^{1+\beta}}(\frac{1}{|V(W)|}\sum_{v\in V(W)}d_v^{1+\beta})
\\ &\ge \frac{1}{|V(W)|^{1+\beta}}(\frac{1}{|V(W)|}\sum_{v\in V(W)}d_v)^{1+\beta}
\\ &= (\frac{1}{|V(W)|^2}\sum_{v\in V(W)}d_v)^{1+\beta}
\\ &= t(P_1, W)^{1+\beta}
\end{align*}

where we have used the power mean inequality.

For the inductive step, suppose $r\ge 2$, and that the statement holds for all $r'<r$. We take two cases.

If $r$ is even, then due to Proposition <ref> and Cauchy-Schwarz,

\begin{align*}
t(P_{0,r,\beta}, W)&\ge t(P_{\frac{\beta}{2}, r, \frac{\beta}{2}}, W)
\\ &\ge t(P_{0, \frac{r}{2}, \frac{\beta}{2}}, W)^2
\\ &\ge t(P_1, W)^{r+\beta}
\end{align*}

where we've used the inductive hypothesis in the last step.

Similarly, if $r$ is odd,

\begin{align*}
t(P_{0,r,\beta}, W)&= t(P_{1, r-1, \beta}, W)
\\ &\ge t(P_{\frac{1+\beta}{2}, r-1, \frac{1+\beta}{2}}, W)
\\ &\ge t(P_{0, \frac{r-1}{2}, \frac{1+\beta}{2}}, W)^2
\\ &\ge t(P_1, W)^{r+\beta}.
\end{align*}

This completes the inductive step, so we are done.

Taking $\beta=0$ in the previous lemma yields the Blakely-Roy inequality, $t(P_n,W)\ge t(P_1,W)^{n}$.

Suppose $k$ is a positive integer, and $G_{k,\ell}$ is the graph on $2k+\ell+1$ vertices consisting of a cycle with length $2k+1$, with one of its vertices connected to an end of a path on $\ell$ edges. Then

\[t(G_{k,\ell}, W)\ge t(C_{2k+1}, W)^{1+\frac{1}{2}\left\lceil\frac{\ell}{k}\right\rceil}.\]

Set $r=\left\lceil\frac{\ell}{2k}\right\rceil$, and $s=2k\lceil\frac{\ell}{2k}\rceil-\ell$. Define a graph $X$ as follows. If $0\le s\le k-1$, then $X$ consists of a $P_{r+1}$, with an additional length $2k$ path added between every pair of adjacent vertices in this base path. If $k\le s\le 2k-1$, then $X$ consists of a $P_r$, with an additional length $2k$ path between every pair of adjacent vertices in the base path, and with an additional length $k$ path attached at one end of the base path. Observe that in either case, $X$ contains $G_{k, \ell}$ as a subgraph. Let $W'$ denote the auxiliary weighted graph, defined by $W(a,b)$ equals the number of ordered cycles in $W$ containing $a,b$ as their first and second vertices, respectively.

We take two cases. First, suppose that $0\le s\le k-1$. Making use of the Lemma <ref>, we have

\begin{align*}t(G_{k, \ell}, W)&\ge t(X, W)
\\&= t(P_{r+1}, W')
\\ &\ge t(P_1,W')^{r+1}
\\ &= t(C_{2k+1}, W)^{r+1}
\\ &=t(C_{2k+1},W)^{1+\lceil\frac{\ell}{2k}\rceil}
\\ &=t(C_{2k+1},W)^{1+\frac{1}{2}\lceil\frac{\ell}{2k}\rceil}.
\end{align*}

Here, we've used the fact that since the difference between $\ell$ and $\ell-2k\lceil\frac{\ell}{2k}\rceil$ is at most $k-1$, it holds that $\lceil\frac{\ell}{k}\rceil=2\lceil\frac{\ell}{2k}\rceil.$

If $r$ is odd, we take a similar approach. We first note that for any given vertex, the number of $P_k$s which start at that vertex is at least the square root of the number of $C_{2k+1}$s containing that vertex, since the square of the first quantity is the number of $P_{2k}$s which have the given vertex as a middle vertex. This means that in the odd case, $t(X, W)\ge t(P_{0,r,\frac{1}{2}}, W')$. Using this, we calculate as before.

\begin{align*}t(G_{k, \ell}, W)&\ge t(X, W)
\\&= t(P_{0,r,\frac{1}{2}}, W')
\\ &\ge t(P_1,W')^{r+1}
\\ &= t(C_{2k+1}, W)^{r+1}
\\ &=t(C_{2k+1},W)^{1+\lceil\frac{\ell}{2k}\rceil}
\\ &=t(C_{2k+1},W)^{1+\frac{1}{2}\lceil\frac{\ell}{2k}\rceil}.
\end{align*}

Now we proceed to the proof of the upper bound. Consider the following auxiliary graph $Y$: start with a cycle $v_1,v_2\ldots, v_{2k+2n}$ on $2k+2n$ vertices, and additionally connect $v_1$ to $v_{2k+1}$ and $v_{2n+1}$. Note that $Y$ contains a $C_{2n+1}$. Using the notation from the previous lemma, an application of <ref> yields:

\begin{align*}t(C_{2n+1},W)&\ge t(Y,W)
\\ &\ge t(G_{k, \ell}, W)^2
\\ &\ge t(C_{2k+1}, W)^{2+\left\lceil\frac{n-k}{k}\right\rceil}
\\ &=t(C_{2k+1}, W)^{1+\left\lceil\frac{n}{k}\right\rceil}
\end{align*}

as desired.

And we can ask a similar question here.

Is it true that, for positive integers $n>k$, $\rho(C_{2k+1}, C_{2n+1})=\frac{n}{k}+o_{k,n}(1)$?

§ COMPLETE AND COMPLETE MULTIPARTITE GRAPHS

We first examine the case where both $G=K_s, H=K_t$ are complete graphs. According to Proposition <ref>, this quantity is finite exactly when $s\ge t$. In this case, $\rho(K_s, K_t)=\frac{t}{s}$ due to Kruskal-Katona [9].

We switch our attention now to complete multipartite graphs. We'll mostly use the convention that indices are always written in nonincreasing order. For a positive integer sequence $\textbf{a}=\{a_1,\ldots, a_n\}$, we write $K_{\bf{a}}$ as shorthand for $K_{a_1,\ldots, a_n}$.

First, two quick lemmas:

Suppose $a,b>1$ are integers. Then, for any graphon $W$,

\[t(K_{a+1,b-1}, W)t(K_{a-1, b+1}, W)\ge t(K_{a,b}, W)^2.\]

Let $K'_{a,b}$ denote the graph obtained by removing an edge from $K_{a,b}$. Then, as a consequence of Proposition <ref>, we have

\[t(K_{a+1,b-1}, W)t(K_{a-1, b+1}, W)\ge t(K'_{a,b}, W)^2\ge t(K_{a,b},W)^2\]

as desired.

For this next lemma, we first define $t(K_{n, x},W)$ where $n$ is a positive integer, $W$ is a graph, and $x$ is a nonnegative real. Namely,

\[t(K_{n,x},W):=\frac{1}{|V(W)|^{n+x}}\sum_{v_1,\ldots, v_n\in V(W)} d_{\{v_1,\ldots, v_n\}}^x.\]

This matches up with the usual definition when $x$ is a nonnegative integer. This allows us to define $\rho(G,H)$ for some of $G,H$ equal to such a $K_{n,x}$.

Suppose that $a,b, c$ be positive integers with $c>a$. Then

\[\rho(K_{c, \frac{bc}{a}}, K_{a,b})=\frac{c}{a}.\]

Taking $W$ to be a single looped vertex in a large, otherwise empty graph yields the required lower bound.

For the upper bound, we make use of a discrete weighted version of Shearer's entropy lemma, found in [5]. Using this, and taking indices modulo $c$ we may calculate:

\begin{align*}
t(K_{c, \frac{bc}{a}}, W)&= \frac{1}{|V(W)|^{c+\frac{cb}{a}}}\sum_{v_1,\ldots, v_c\in V(W)} d_{\{v_1,\ldots, v_c\}}^{\frac{cb}{a}}.
\\ &\le \frac{1}{|V(W)|^{c+\frac{cb}{a}}}\sum_{v_1,\ldots, v_c\in V(W)} \prod_{i=1}^cd_{\{v_i,\ldots, v_{i+a-1}\}}^{\frac{b}{a}}.
\\ &\le (\frac{1}{|V(W)|^{a+b}}\sum_{v_1,\ldots, v_a\in V(W)} d_{\{v_1,\ldots, v_{a}\}}^b)^{\frac{c}{a}}
\\ &= t(K_{a,b}, W)^{\frac{c}{a}}
\end{align*}

as desired.

Now we characterize $\rho(G,H)$ for most complete bipartite graphs $G,H$.

Let $a_1\ge a_2, b_1\ge b_2$ be positive integers. Then

\[\rho(K_{a_1, a_2}, K_{b_1, b_2})=\begin{cases}
\frac{b_1b_2}{a_1a_2} & b_1\ge a_1, b_2\ge a_2
\\ \frac{b_2}{a_2} & b_1\le a_1, b_2\ge a_2
\\ \max\{\frac{b_2}{a_2}, \frac{b_1+b_2}{a_1+a_2}\} & b_1\le a_1, b_2\le a_2
\\ \frac{b_1+b_2}{a_1+a_2} & b_1\ge a_1, b_2\le a_2, b_1+b_2\le a_1+a_2
\\ \frac{b_1}{a_1+a_2-1} & b_1\ge a_1, b_2=1, b_1+b_2\ge a_1+a_2
\end{cases}.\]

As usual, the lower bounds are all cases of Proposition <ref>. In particular, the first bound follows from (a), the second through fourth follow from (b) and (d), and the fifth follows from (c).

We turn our attention to the upper bounds. Suppose first that $b_1\ge a_1$ and $b_2\ge a_2$. Define $K_{i, 0}=K_{0,i}$ to be the empty graph on $i$ vertices, so that $t(K_{i,0}, W)=1$ for any $t, W$. Then, using Proposition <ref> twice,

\begin{align*}
t(K_{b_1,b_2}, W)^{a_1a_2}&= (t(K_{b_1,b_2},W)^a_1t(K_{0,b_2},W)^{b_1-a_1})^{a_2}
\\ &\ge t(K_{a_1, b_2},W)^{b_1a_2}
\\ &= (t(K_{a_1,b_2},W)^{a_2}t(K_{a_1,0},W)^{b_2-a_2})^{b_1}
\\ &\ge t(K_{a_1,a_2}, W)^{b_1b_2}
\end{align*}

as desired.

The second upper bound (for the case $b_1\le a_1, b_2\ge a_2$)  follows from the first as follows.

\[t(K_{b_1,b_2},W)\ge t(K_{b_1, a_2},W)^{\frac{b_2}{a_2}}\ge t(K_{a_1, a_2},W)^{\frac{b_2}{a_2}},\]

where the last line holds because $K_{b_1, a_2}$ is a subgraph of $K_{a_1, a_2}$.

For the third upper bound, we take two cases. If $\frac{b_2}{a_2}\ge \frac{b_1}{a_1}$, then the maximum is equal to $\frac{b_2}{a_2}$. In this case, we find that

\[t(K_{b_1,b_2},W)\ge t(K_{\frac{b_1a_2}{b_2}, a_2}, W)^{\frac{b_2}{a_2}}\ge t(K_{a_1, a_2}, W)^{\frac{b_2}{a_2}}\]

due to Lemma <ref>.

On the other hand, if $\frac{b_2}{a_2}\le \frac{b_1}{a_1}$, then the maximum is $\frac{b_1+b_2}{a_1+a_2}$. In this case, we can calculate:

\begin{align*}
t(K_{b_1,b_2}, W)^{(a_1+a_2)(\frac{a_1}{b_2}-\frac{a_1}{b_1})}&=t(K_{b_1,b_2},W)^{\frac{a_1^2}{b_2}-\frac{a_1a_2}{b_1}}t(K_{b_1,b_2},W)^{\frac{a_1a_2}{b_2}-\frac{a_1^2}{b_1}}
\\ &\ge t(K_{a_1, \frac{a_1b_2}{b_1}}, W)^{\frac{a_1b_1}{b_2}-a_2}t(K_{a_1, \frac{a_1b_1}{b_2}}, W)^{a_2-\frac{a_1b_2}{b_1}}
\\ &\ge t(K_{a_1, a_2}, W)^{(b_1+b_2)(\frac{a_1}{b_2}-\frac{a_1}{b_1})}
\end{align*}

as desired.

Now we turn our focus to the fourth upper bound. The approach here is to reduce to the previous case via Lemma <ref>. Indeed,

\[t(K_{b_1,b_2},W)\ge t(K_{b_1, a_1+a_2-b_1}, W)^{\frac{b_1+b_2}{a_1+a_2}}\ge t(K_{a_1, a_2}, W)^{\frac{b_1+b_2}{a_1+a_2}}.\]

Finally, the fifth upper bound follows directly from Proposition <ref>.

There's one case remaining. We conjecture the right answer for this missing case.

Let $a_1\ge a_2, b_1\ge b_2$ be positive integers with $a_2\ge b_2>1, a_1\le b_1, b_1+b_2\ge a_1+a_2$. Then

\[\rho(K_{a_1,a_2},K_{b_1,b_2})=\max\{\frac{b_1b_2}{a_1a_2}, \frac{b_1+b_2-1}{a_1+a_2-1}\}.\]

We can extend these results partially to the general multipartite case via the following result:

Let $\bf{a}, \bf{b}$ be length $k$ sequences of positive integers such that $a\succ b$. Then

\[\rho(K_{\bf b}, K_{\bf a})=1.\]

Furthermore, if $||\bf a||_1=||\bf b||_1$, then this equality holds if and only if $a\succ b$.

For the lower bound, take construction (b) from Proposition <ref>.

For the upper bound, we prove a lemma:

Suppose $\bf a,\bf b$ are length $k$ positive integer vectors with $\bf a\succ\bf b$. Then there exists a sequence $\bf a=\bf a_0, \bf a_1, \ldots, \bf a_\ell=\bf b$ such that, for each $0\le i\le \ell-1$, the vectors $\bf a_i$ and $\bf a_{i+1}$ differ in at most two coordinates, and $\bf a_i\succ \bf a_{i+1}$.

We induct on $\sum_{i=1}^k(\sum_{j=1}^i(a_j-b_j))$. Note that due to the majorization condition, this quantity is always nonnegative. For the base case, if the summation is zero, then $\bf a=\bf b$ and the result is clear.

Otherwise, $\bf a\neq \bf b$, which means that they differ in at least two indices. Let $r$ be the lowest index for which $b_r\neq a_r$, and let $s>r$ be the greatest index for which $b_s=b_{r+1}$. Let $\bf{b'}$ be the nonnegative integer vector obtained by adding one to the $r$th index of $\bf b$ and subtracting one from the $s$th index. Note that the indices of $\bf{b'}$ are still in nonincreasing order. We claim $\bf a\succ \bf{b'}\succ \bf{b}$. The latter majorization is clear. For the former, we just need to prove the inequality $\sum_{j=1}^i (a_j-b_j)\ge 0$ for each $1\le j\le k$. We take three cases.

If $i\le r-1$ or $i\ge s$, then $\sum_{j=1}^i b_j=\sum_{j=1}^i b_j'$, and so the inequality follows from the majorization $\bf a\succ\bf b$.

If $i=r$, then $\bf b_i'\le \bf a_i$ and $\bf b'_j=\bf b_j=\bf a_j$ for $j<i$, so the result follows.

For $r+1\le i\le s-1$, we argue via contradiction. Suppose that the inequality does not hold. Since the summation shifts by $1$ from $\bf b$ to $\bf b'$ in this regime and $\bf a\succ \bf b$, it must be the case that $\sum_{j=1}^ia_j=\sum_{j=1}^i b_j$. Since $a_r>b_r$ and $a_j=b_j$ for $j<r$, there exists some index $\ell\in [r+1, j]$ such that $a_\ell<b_\ell$. But then $a_i\le a_\ell<b_\ell=b_i$. Hence $\sum_{j=1}^{i-1}a_j<\sum_{j=1}^{i-1} b_j$, contradicting $\bf a\succ \bf b$. Hence, $\bf a\succ \bf{b'}$ as required.

Now $\bf{b'}$ and $\bf{b}$ differ in at most two indices, and $\sum_{i=1}^k(\sum_{j=1}^i(a_j-b'_j))<\sum_{i=1}^k(\sum_{j=1}^i(a_j-b_j))$, so by the inductive hypothesis we can find a chain from $\bf a$ to $\bf {b'}$. This completes the inductive step, so we're done.

Due to the lemma, to prove the upper bound, it suffices to check that $t(K_{\bf a},W)\ge t(K_{\bf b}, W)$ when $\bf a\succ \bf b$ and $\bf a,\bf b$ differ in only two indices. This follows directly from an application of Lemma <ref>, so we are done.

For the converse, suppose that the majorization fails at index $i$; that is, $\sum_{j=1}^ia_j<\sum_{j=1}^ib_j$. Then take $W$ to be a complete $k$-partite graph with $i$ parts having size $n$ for large $n$ and the remaining $k-i$ parts having size $1$. Then $t(\bf {a}, W)$ is $\Theta(n^{\sum_{j=1}^ia_j-||\bf a||_1})$, while $t(\bf {b}, W)$ is $\Theta(n^{\sum_{j=1}^ib_j-||\bf b||_1})$, so $\rho(K_{\bf b}, K_{\bf a})\ge \frac{\log t(\bf {a}, W)}{\log t(\bf {b}, W)}>1$ for large enough $n$, as desired.

Denote by $K'_{a_1, \ldots, a_n}$ the $n$-partite graph $G$ defined as follows. $G$ contains a central clique $C$, with vertices $v_1, \ldots, v_n$, and for each $i$, $G$ contains $a_i$ vertices outside of $C$ which have neighborhood $C-\{v_i\}$.

For any nonnegative integer vector $\bf{a}=\{a_1,\ldots, a_n\}$,

\[\rho(K_n, K'_{\bf{a}})=1+||\bf{a}||_1.\]

The lower bound construction can be found in [7]. Indeed, for each $n$, this paper gives a family of graphs on $N$ vertices for $N$ sufficiently large which have $K_n$ density $N^{-1+o(1)}$ and $K'_{\bf{a}}$ density $N^{-1-||\bf{a}||_1+o(1)}$.

We turn to the upper bound; let $W$ be any graph. Let $\mathcal{R}$ denote the family of ordered vertex subsets of size $n$ made from the vertices in $W$ which form a $K_n$.  Then

\begin{align*}
t(K'_{\bf{a}}, W)&= \frac{1}{|V(W)|^{||\bf{a}||_1+n}}\sum_{S\in \mathcal{R}\atop S=\{v_1,\ldots v_n\}} \prod_{i=1}^nd_{S\sm v_i}^{a_i}
\\ &\ge \frac{1}{|V(W)|^{||\bf{a}||_1+n}}(\sum_{S\in \mathcal{R}\atop S=\{v_1,\ldots v_n\}} \prod_{i=1}^nd_{S\sm v_i}^{a_i})t(K_{n-1}, W)^{||\bf{a}||_1}
\\ &=\frac{1}{|V(W)|^{n(||\bf{a}||_1+1)}}(\sum_{S\in \mathcal{R}\atop S=\{v_1,\ldots v_n\}} \prod_{i=1}^nd_{S\sm v_i}^{a_i})\prod_{i=1}^n(\sum_{S\in \mathcal{R}\atop S=\{v_1,\ldots v_n\}}d_{S\sm v_i}^{-1})^{a_i}
\\ &\ge (\frac{1}{|V(W)|^n}\sum_{S\in \mathcal{R}} 1)^{1+||\bf{a}||_1}
\\ &= t(K_n, W)^{1+||\bf{a}||_1}
\end{align*}

as desired.

The above theorem is also true if the graphs are replaced with $n$-uniform hypergraphs where every copy of $K_n$ induces a hyperedge. The lower bound construction in this case is much easier; just take $W$ to be a uniformly pseudorandom hypergraph.

§ OPEN PROBLEMS

Here, we summarize some of the remaining open problems, including some minimal open values of $\rho(G,H)$.
What is the value of $\rho(C_3,C_4)$?

We know $\rho(C_3, C_4)\in [\frac{3}{2}, \frac{8}{5}].$ The lower bound is given by Proposition <ref>, construction c.  The upper bound follows from the following inequality chain:

\begin{align*}t(C_4, W)^5&=t(\squ, W)^5
\\&\ge t(\edge, W)^4t(\squ, W)^4
\\&\ge t(\edge, W)^4t(\squz, W)^4
\\&\ge t(\tri, W)^8
\\ &= t(C_3, W)^8.
\end{align*}

The first inequality is due to $C_4$ being a Sidorenko graph, while the third is an application of Proposition <ref>.

What is the value of $\rho(P_5,P_3)$?
We know $\rho(P_5,P_3)\in [\frac{7}{10}, \frac{3}{4}].$ The lower bound is the construction from [10]. The upper bound follows from the following inequality chain:

\[t(P_3, W)^4\ge t(P_{15}, W)\ge t(P_5, W)^3.\]

The first inequality is true since $P_{15}$ contains four vertex-disjoint copies of $P_3$, while the second is an instance of Theorem <ref>.

The following question is a natural one, given the nature of the results found here.

For graphs $G,H$ for which $\rho(G,H)$ exists and is finite, is it always rational? Algebraic?

Given the existence of Proposition 2.7 and other anomalies, it seems likely that a finite number of sequences cannot cover all cases. That is, the following seems likely to hold true.

Is it true that, for every finite family of graphon sequences $\mathcal{F}$, there exists some graphs $G,H$ for which $\rho(G,H)$ is finite and $\frac{\log t(H,W_n)}{\log t(G,W_n)}$ does not converge to $\rho(G,H)$ as $n\to\infty$ for any $\{W_n\}\in \mathcal{F}$?

Finally, Theorem <ref> motivates the following general question.

Let $H$ be any $n$-partite $n$-uniform hypergraph, and let $H^*$ denote the $2$-graph where a pair of vertices is connected by an edge in $H^*$ if and only if they are both in a hyperedge of $H$.  Is it always the case that $\rho(K_n, H)=\rho(K_n^*, H^*)$?

title=A partially ordered set of functionals corresponding to graphs,
author=Sidorenko, Alexander,
journal=Discrete Mathematics,

title=Threshold graphs maximize homomorphism densities,
author=Blekherman, Grigoriy and Patel, Shyamal,
journal=arXiv preprint arXiv:2002.12117,

title=On the Density of a Graph and its Blowup,
author=Asaf Shapira and Raphael Yuster,

title=Triforce and corners,
author=Fox, Jacob and Sah, Ashwin and Sawhney, Mehtaab and Stoner, David and Zhao, Yufei,
booktitle=Mathematical Proceedings of the Cambridge Philosophical Society,
organization=Cambridge University Press

title=On the number of subgraphs of prescribed type of graphs with a given number of edges,
author=Alon, Noga,
journal=Israel Journal of Mathematics,

title=Sidorenko's conjecture, graph norms, and pseudorandomness,
author=Lee, Joonkyung,
school=University of Oxford

title=Hypergraphs, entropy, and inequalities,
author=Friedgut, Ehud,
journal=The American Mathematical Monthly,
publisher=Taylor & Francis

title=Proof of the Erdos-Simonovits conjecture on walks,
author=Blekherman, Grigoriy and Raymond, Annie,
journal=arXiv preprint arXiv:2009.10845,

title=The homomorphism domination exponent,
author=Kopparty, Swastik and Rossman, Benjamin,
journal=European Journal of Combinatorics,

title=On the number of copies of one hypergraph in another,
author=Friedgut, Ehud and Kahn, Jeff,
journal=Israel Journal of Mathematics,

title=Two approaches to Sidorenko’s conjecture,
author=Kim, Jeong Han and Lee, Choongbum and Lee, Joonkyung,
journal=Transactions of the American Mathematical Society,

[1]
Noga Alon, On the number of subgraphs of prescribed type of graphs with a given number of edges, Israel J. Math. 38 (1981), 116-130.
[2]
Grigoriy Blekherman and Shyamal Patel, Threshold graphs maximize homomorphism densities, arXiv:2002.12117.
[3]
Grigoriy Blekherman and Annie Raymond, Proof of the Erdős-Simonovits conjecture on walks, (2020), arXiv:2009.10845.
[4]
Jacob Fox, Ashwin Sah, Mehtaab Sawhney, Cynthia Stoner, and Yufei Zhao, Triforce and corners, Math. Proc. Cambridge Philos. Soc.
[5]
Ehud Friedgut, Hypergraphs, entropy, and inequalities, Amer. Math. Monthly 111 (2004), 749–760.
[6]
Ehud Friedgut and Jeff Kahn, On the number of copies of one hypergraph in another, Israel J. Math. 105 (1998), 1097–1114.
[7]
William Timothy Gowers and Barnabas Janzer, Generalizations of the Ruzsa-Semeredi and rainbow Turan problems for cliques, Combin. Probab. Comput. 30 (2021), 591-608
[8]
Jeong Han Kim, Choongbum Lee, and Joonkyung Lee, Two approaches to Sidorenko's conjecture, Trans. Amer. Math. Soc. 368 (2016), 5057–5074.
[9]
Joseph Kruskal, The number of simplices in a complex, Math. Optim. Tech. (1963)
[10]
Swastik Kopparty and Benjamin Rossman, The homomorphism domination exponent, European J. Combin. 105 (1998), 251–256.
[11]
Joonkyung Lee, Sidorenko's conjecture, graph norms, and pseudorandomness, PhD Thesis, University of Oxford (2017), 132 pp.
169 (2020), 209-223.
[12]
Asaf Shapira and Raphael Yuster, On the Density of a Graph and its Blowup, arXiv:0903.0198.
[13]
Alexander Sidorenko, A partially ordered set of functionals corresponding to graphs,  Discrete Math. 131 (1994), 263-277.