Journal: Acta Mathematica Hungarica

Abbreviation

Acta math. Hung. (Print)

Publisher

Springer

Journal Volumes

ISSN

0236-5294
1588-2632

Description

Filters

2012 - 201932020 - 20252
Reset filters

Search Results

Publications 1 - 5 of 5
  • Multifactorial inheritance with selection
    Item type: Journal Article
    Gerencsér, Balázs; Ráth, Balázs; Tusnády, Gábor (2013)
    Acta Mathematica Hungarica
  • Multigraph limit of the dense configuration model and the preferential attachment graph
    Item type: Journal Article
    Rath, B.; Szakacs, L. (2012)
    Acta Mathematica Hungarica
  • On the diameter of finite Sidon sets
    Item type: Journal Article
    Carter, Daniel; Hunter, Zach; O'Bryant, Kevin (2025)
    Acta Mathematica Hungarica
  • Partitions of the set of natural numbers and symplectic homology
    Item type: Journal Article
    Uljarevic, Igor (2018)
    Acta Mathematica Hungarica
  • Colorings with only rainbow arithmetic progressions
    Item type: Journal Article
    Pach, János; Tomon, István (2020)
    Acta Mathematica Hungarica
    If we want to color 1, 2, ... , n with the property that all 3-term arithmetic progressions are rainbow (that is, their elements receive 3 distinct colors), then, obviously, we need to use at least n/2 colors. Surprisingly, much fewer colors suffice if we are allowed to leave a negligible proportion of integers uncolored. Specifically, we prove that there exist alpha, beta < 1 such that for every n, there is a subset A of {1, 2, ... , n} of size at least n - n(alpha), the elements of which can be colored with n(beta) colors with the property that every 3-term arithmetic progression in A is rainbow. Moreover, beta can be chosen to be arbitrarily small. Our result can be easily extended to k-term arithmetic progressions for any k >= 3. As a corollary, we obtain a simple proof of the following result of Alon, Moitra, and Sudakov, which can be used to design efficient communication protocols over shared directional multi-channels. There exist alpha', beta' < 2 such that for every n, there is a graph with n vertices and at least ((n)(2)) - n(alpha)' edges, whose edge set can be partitioned into at most n(beta)' induced matchings.
Publications 1 - 5 of 5