All binomial identities are orderable

DOI10.1016/J.EJC.2016.11.008MaRDI QIDQ730270zbMATH OpenOpenAlexFDO

Authors Dmitry N. Kozlov

Publication date 27 December 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.08743

zbMATH Keywords

fundamental binomial identity

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19)

Abstract: The main result of this paper is to show that all binomial identities are orderable. This is a natural statement in the combinatorial theory of finite sets, which can also be applied in distributed computing to derive new strong bounds on the round complexity of the weak symmetry breaking task. Furthermore, we introduce the notion of a fundamental binomial identity and find an infinite family of values, other than the prime powers, for which no fundamental binomial identity can exist.

Recommendations

• scientific article; zbMATH DE number 4099304
• scientific article; zbMATH DE number 4041924
• Binomial identities -- combinatorial and algorithmic aspects
• scientific article; zbMATH DE number 3843753
• Identities in order statistics – from moments to arbitrary distributions

Cites work

• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• scientific article; zbMATH DE number 1792287 (Why is no real title available?)
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Distributed computing through combinatorial topology
• Matching theory
• New combinatorial topology bounds for renaming: the upper bound
• Upper bound on the complexity of solving hard renaming

Cited in

(3)

• Structure theory of flip graphs with applications to weak symmetry breaking
• Bounds on the step and namespace complexity of renaming
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes

This page was built for publication: All binomial identities are orderable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730270)