On the discrepancies of graphs

József Balogh; Béla Csaba; Yifan Jing; András Pluhár

doi:10.37236/8425

On the discrepancies of graphs

József Balogh
, Béla Csaba
, Yifan Jing
, András Pluhár

Mathematics

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

Abstract

In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph G with each edge labelled 1 or 1, we consider a family SG of subgraphs of a certain type, such as spanning trees or Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of SG, for every labeling.

Original language	English (US)
Article number	P2.12
Journal	Electronic Journal of Combinatorics
Volume	27
Issue number	2
DOIs	https://doi.org/10.37236/8425
State	Published - 2020

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Online availability

10.37236/8425

Library availability

Discover UIUC Full Text

Cite this

@article{c94442e2ecc94b14b688db10fccbde92,

title = "On the discrepancies of graphs",

abstract = "In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph G with each edge labelled 1 or 1, we consider a family SG of subgraphs of a certain type, such as spanning trees or Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of SG, for every labeling.",

author = "J{\'o}zsef Balogh and B{\'e}la Csaba and Yifan Jing and Andr{\'a}s Pluh{\'a}r",

note = "∗The first author is partially supported by NSF Grant DMS-1500121 and DMS-1764123, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132) and the Langan Scholar Fund (UIUC). †The second author was partially supported by the Ministry of Human Capacities, Hungary, Grant 20391-3/2018/FEKUSTRAT. ‡The second and fourth authors were partially supported by the NKFIH grants KH 18 129597 and SNN 117879.",

year = "2020",

doi = "10.37236/8425",

language = "English (US)",

volume = "27",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Australian National University",

number = "2",

}

TY - JOUR

T1 - On the discrepancies of graphs

AU - Balogh, József

AU - Csaba, Béla

AU - Jing, Yifan

AU - Pluhár, András

N1 - ∗The first author is partially supported by NSF Grant DMS-1500121 and DMS-1764123, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132) and the Langan Scholar Fund (UIUC). †The second author was partially supported by the Ministry of Human Capacities, Hungary, Grant 20391-3/2018/FEKUSTRAT. ‡The second and fourth authors were partially supported by the NKFIH grants KH 18 129597 and SNN 117879.

PY - 2020

Y1 - 2020

N2 - In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph G with each edge labelled 1 or 1, we consider a family SG of subgraphs of a certain type, such as spanning trees or Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of SG, for every labeling.

AB - In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph G with each edge labelled 1 or 1, we consider a family SG of subgraphs of a certain type, such as spanning trees or Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of SG, for every labeling.

UR - https://www.scopus.com/pages/publications/85083966231

UR - https://www.scopus.com/pages/publications/85083966231#tab=citedBy

U2 - 10.37236/8425

DO - 10.37236/8425

M3 - Article

AN - SCOPUS:85083966231

SN - 1077-8926

VL - 27

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - P2.12

ER -

On the discrepancies of graphs

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this