The smallestn-uniform hypergraph with positive discrepancy View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1987-06

AUTHORS

N. Alon, D. J. Kleitman, C. Pomerance, M. Saks, P. Seymour

ABSTRACT

A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erdős and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc1 andc2 such that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ \end{document} where snd(x) is the least positive integer that does not dividex. More... »

PAGES

151-160

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02579446

DOI

http://dx.doi.org/10.1007/bf02579446

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1002866381


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tel Aviv University Ramat Aviv, 69978, Tel Aviv, Israel", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Tel Aviv University Ramat Aviv, 69978, Tel Aviv, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alon", 
        "givenName": "N.", 
        "id": "sg:person.0765221225.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765221225.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleitman", 
        "givenName": "D. J.", 
        "id": "sg:person.0761443440.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0761443440.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pomerance", 
        "givenName": "C.", 
        "id": "sg:person.0637766244.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0637766244.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "M.", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seymour", 
        "givenName": "P.", 
        "id": "sg:person.011037242241.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037242241.09"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02579453", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040497259", 
          "https://doi.org/10.1007/bf02579453"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1987-06", 
    "datePublishedReg": "1987-06-01", 
    "description": "A two-coloring of the verticesX of the hypergraphH=(X, \u03b5) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd\u0151s and S\u00f3s asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc1 andc2 such that\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\frac{{c_1 \\log (snd(n/2))}}{{\\log \\log (snd(n/2))}} \\leqq f(n) \\leqq c_2 \\frac{{\\log ^3 (snd(n/2))}}{{\\log \\log (snd(n/2))}}$$\n\\end{document} where snd(x) is the least positive integer that does not dividex.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02579446", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "keywords": [
      "positive discrepancy", 
      "differences", 
      "number", 
      "half", 
      "IFD", 
      "large differences", 
      "discrepancy", 
      "point", 
      "questions", 
      "verticesx", 
      "least positive integer", 
      "blue points", 
      "edge", 
      "two-coloring", 
      "ofH", 
      "andC2", 
      "positive integer", 
      "number of edges", 
      "hypergraphs", 
      "Erd\u0151s", 
      "S\u00f3s", 
      "integers"
    ], 
    "name": "The smallestn-uniform hypergraph with positive discrepancy", 
    "pagination": "151-160", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002866381"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02579446"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02579446", 
      "https://app.dimensions.ai/details/publication/pub.1002866381"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_201.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02579446"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02579446'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02579446'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02579446'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02579446'


 

This table displays all metadata directly associated to this object as RDF triples.

117 TRIPLES      21 PREDICATES      48 URIs      39 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02579446 schema:about anzsrc-for:01
2 anzsrc-for:08
3 schema:author N0b3a765779e74530860b1862b488cffe
4 schema:citation sg:pub.10.1007/bf02579453
5 schema:datePublished 1987-06
6 schema:datePublishedReg 1987-06-01
7 schema:description A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erdős and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc1 andc2 such that\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ \end{document} where snd(x) is the least positive integer that does not dividex.
8 schema:genre article
9 schema:isAccessibleForFree true
10 schema:isPartOf N1a227d9112064c478eea85e8d55b684c
11 Ne479bef2921a41e89835969903b28a7d
12 sg:journal.1136493
13 schema:keywords Erdős
14 IFD
15 Sós
16 andC2
17 blue points
18 differences
19 discrepancy
20 edge
21 half
22 hypergraphs
23 integers
24 large differences
25 least positive integer
26 number
27 number of edges
28 ofH
29 point
30 positive discrepancy
31 positive integer
32 questions
33 two-coloring
34 verticesx
35 schema:name The smallestn-uniform hypergraph with positive discrepancy
36 schema:pagination 151-160
37 schema:productId N40e4db90d1c44eaf9fda87d51956359a
38 N9551c0d7915549dea54b17d90c7834b4
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002866381
40 https://doi.org/10.1007/bf02579446
41 schema:sdDatePublished 2022-10-01T06:28
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N0a56977b36b54e88b8c94d65d51e81d8
44 schema:url https://doi.org/10.1007/bf02579446
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N0a56977b36b54e88b8c94d65d51e81d8 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N0b3a765779e74530860b1862b488cffe rdf:first sg:person.0765221225.03
51 rdf:rest Nf097a31c1df24825b4630d8e4e690efc
52 N1a227d9112064c478eea85e8d55b684c schema:issueNumber 2
53 rdf:type schema:PublicationIssue
54 N315a80b097a04a76820467fe8b0c5748 rdf:first sg:person.0637766244.56
55 rdf:rest Nf2764a69c4ca4dbbac342f1ad05767b0
56 N40e4db90d1c44eaf9fda87d51956359a schema:name doi
57 schema:value 10.1007/bf02579446
58 rdf:type schema:PropertyValue
59 N9391705fe4ee436f814a4371d79fa2ff rdf:first sg:person.011037242241.09
60 rdf:rest rdf:nil
61 N9551c0d7915549dea54b17d90c7834b4 schema:name dimensions_id
62 schema:value pub.1002866381
63 rdf:type schema:PropertyValue
64 Ne479bef2921a41e89835969903b28a7d schema:volumeNumber 7
65 rdf:type schema:PublicationVolume
66 Nf097a31c1df24825b4630d8e4e690efc rdf:first sg:person.0761443440.18
67 rdf:rest N315a80b097a04a76820467fe8b0c5748
68 Nf2764a69c4ca4dbbac342f1ad05767b0 rdf:first sg:person.011520224512.05
69 rdf:rest N9391705fe4ee436f814a4371d79fa2ff
70 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
71 schema:name Mathematical Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 sg:journal.1136493 schema:issn 0209-9683
77 1439-6912
78 schema:name Combinatorica
79 schema:publisher Springer Nature
80 rdf:type schema:Periodical
81 sg:person.011037242241.09 schema:affiliation grid-institutes:grid.432790.b
82 schema:familyName Seymour
83 schema:givenName P.
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037242241.09
85 rdf:type schema:Person
86 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.432790.b
87 schema:familyName Saks
88 schema:givenName M.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
90 rdf:type schema:Person
91 sg:person.0637766244.56 schema:affiliation grid-institutes:grid.432790.b
92 schema:familyName Pomerance
93 schema:givenName C.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0637766244.56
95 rdf:type schema:Person
96 sg:person.0761443440.18 schema:affiliation grid-institutes:grid.116068.8
97 schema:familyName Kleitman
98 schema:givenName D. J.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0761443440.18
100 rdf:type schema:Person
101 sg:person.0765221225.03 schema:affiliation grid-institutes:grid.12136.37
102 schema:familyName Alon
103 schema:givenName N.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765221225.03
105 rdf:type schema:Person
106 sg:pub.10.1007/bf02579453 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040497259
107 https://doi.org/10.1007/bf02579453
108 rdf:type schema:CreativeWork
109 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, 02139, Cambridge, MA, USA
110 schema:name Massachusetts Institute of Technology, 02139, Cambridge, MA, USA
111 rdf:type schema:Organization
112 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University Ramat Aviv, 69978, Tel Aviv, Israel
113 schema:name Tel Aviv University Ramat Aviv, 69978, Tel Aviv, Israel
114 rdf:type schema:Organization
115 grid-institutes:grid.432790.b schema:alternateName Bell Communications Research, 07960, Morristown, NJ, USA
116 schema:name Bell Communications Research, 07960, Morristown, NJ, USA
117 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...