talk on A352178

[Max Alekseyev]

Dear SeqFans,

In case you missed my talk on the sequence A352178 at Doron Zeilberger's experimental math seminar yesterday, here is its recording:

https://vimeo.com/1136694072

Title: Maximizing the number of integer pairs summing to powers of 2 via graph labeling and solving restricted systems of linear (in)equations

Abstract: We address the problem of finding sets of integers of a given size with a maximum number of pairs summing to powers of 2. By fixing particular pairs, this problem reduces to finding a labeling of the vertices of a given graph with pairwise distinct integers such that the endpoint labels for each edge sum up to a power of 2. We propose an efficient algorithm for this problem, which at its core relies on another algorithm that, given two sets of linear homogeneous polynomials with integer coefficients, computes all variable assignments to powers of 2 that nullify polynomials from the first set but not from the second. With the proposed algorithms, we determine the maximum size of graphs of order n that admit such a labeling for all n<=21, and construct the maximum admissible graphs for n<=20. We also identify the minimal forbidden subgraphs of order n<=11, whose presence prevents the graphs from having such a labeling.

Preprint: https://arxiv.org/abs/2303.02872

SageMath code: https://github.com/maxale/power2_graphs

Regards,

Max