Graph partition method based on finite projective planes

Anna Mastikhina; Dmitry Sirotkin; Oleg Kruglov; Oleg Senkevich; Stanislav Moiseev

Graph partition method based on finite projective planes

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2312.13861 v1 pith:5HH77LGY submitted 2023-12-21 math.CO

Graph partition method based on finite projective planes

Oleg Kruglov , Anna Mastikhina , Oleg Senkevich , Dmitry Sirotkin , Stanislav Moiseev This is my paper

classification math.CO

keywords sqrtgraphpartitionalgorithmapproachesbetterboundconstrained

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original abstract

We present a novel graph partition algorithm with a theoretical bound for the replication factor of \sqrt(n), which improves known constrained approaches (grid: 2* \sqrt(n)-1, torus: 1.5*\sqrt(n)+1) and provides better performance

discussion (0)

Forward citations

Cited by 1 Pith paper

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

Fundamental Limits of Hypergraph Edge Partitioning under Independent Edge Sampling
cs.IT 2026-06 unverdicted novelty 7.0

The minimal achievable vertex footprint for hypergraph edge partitioning under independent edge sampling is (1/(2√2)) n / N^{1/d}, with a deterministic partitioner achieving it up to a small constant factor.