Standard

On small n-uniform hypergraphs with positive discrepancy. / Cherkashin, Danila; Petrov, Fedor.

In: Journal of Combinatorial Theory. Series B, Vol. 139, 01.11.2019, p. 353-359.

Research output: Contribution to journal › Article › peer-review

Harvard

Cherkashin, D & Petrov, F 2019, 'On small n-uniform hypergraphs with positive discrepancy', Journal of Combinatorial Theory. Series B, vol. 139, pp. 353-359. https://doi.org/10.1016/j.jctb.2019.04.001

APA

Cherkashin, D., & Petrov, F. (2019). On small n-uniform hypergraphs with positive discrepancy. Journal of Combinatorial Theory. Series B, 139, 353-359. https://doi.org/10.1016/j.jctb.2019.04.001

Vancouver

Cherkashin D, Petrov F. On small n-uniform hypergraphs with positive discrepancy. Journal of Combinatorial Theory. Series B. 2019 Nov 1;139:353-359. https://doi.org/10.1016/j.jctb.2019.04.001

Author

Cherkashin, Danila ; Petrov, Fedor. / On small n-uniform hypergraphs with positive discrepancy. In: Journal of Combinatorial Theory. Series B. 2019 ; Vol. 139. pp. 353-359.

BibTeX

@article{4f04f5614ddf46fb959bf5e7009d4d3b,
title = "On small n-uniform hypergraphs with positive discrepancy",
abstract = "A two-coloring of the vertices V of the hypergraph H=(V,E) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. Let f(n) be the fewest number of edges in an n-uniform hypergraph without a coloring with discrepancy 0. Erd{\H o}s and S{\'o}s asked: is f(n) unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour [1] proved upper and lower bounds in terms of the smallest non-divisor (snd) of n (see (1)). We refine the upper bound as follows: f(n)≤clog⁡sndn.",
keywords = "Hypergraph colorings, Hypergraph discrepancy, Prescribed matrix determinant",
author = "Danila Cherkashin and Fedor Petrov",
note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",
year = "2019",
month = nov,
day = "1",
doi = "10.1016/j.jctb.2019.04.001",
language = "English",
volume = "139",
pages = "353--359",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On small n-uniform hypergraphs with positive discrepancy

AU - Cherkashin, Danila

AU - Petrov, Fedor

N1 - Publisher Copyright: © 2019 Elsevier Inc.

PY - 2019/11/1

Y1 - 2019/11/1

N2 - A two-coloring of the vertices V of the hypergraph H=(V,E) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. Let f(n) be the fewest number of edges in an n-uniform hypergraph without a coloring with discrepancy 0. Erdős and Sós asked: is f(n) unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour [1] proved upper and lower bounds in terms of the smallest non-divisor (snd) of n (see (1)). We refine the upper bound as follows: f(n)≤clog⁡sndn.

AB - A two-coloring of the vertices V of the hypergraph H=(V,E) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. Let f(n) be the fewest number of edges in an n-uniform hypergraph without a coloring with discrepancy 0. Erdős and Sós asked: is f(n) unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour [1] proved upper and lower bounds in terms of the smallest non-divisor (snd) of n (see (1)). We refine the upper bound as follows: f(n)≤clog⁡sndn.

KW - Hypergraph colorings

KW - Hypergraph discrepancy

KW - Prescribed matrix determinant

UR - http://www.scopus.com/inward/record.url?scp=85064004832&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2019.04.001

DO - 10.1016/j.jctb.2019.04.001

M3 - Article

AN - SCOPUS:85064004832

VL - 139

SP - 353

EP - 359

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -

ID: 41502534