Bipartite Turán Problems for Ordered Graphs Abhishek Methuku, István Tomon View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-01-14

AUTHORS

Abhishek Methuku, István Tomon

ABSTRACT

A zero-one matrix M contains a zero-one matrix A if one can delete some rows and columns of M, and turn some 1-entries into 0-entries such that the resulting matrix is A. The extremal number of A, denoted by ex(n, A), is the maximum number of 1-entries in an n × n sized matrix M that does not contain A.A matrix A is column-t-partite (or row-t-partite), if it can be cut along the columns (or rows) into t submatrices such that every row (or column) of these submatrices contains at most one 1-entry. We prove that if A is column-t-partite, then ex(nA) More... »

PAGES

1-17

References to SciGraph publications

  • 2006-12. Forbidden paths and cycles in ordered graphs and matrices in ISRAEL JOURNAL OF MATHEMATICS
  • 1991-03. On a Turán type problem of Erdös in COMBINATORICA
  • 1996-09. Norm-graphs and bipartite turán numbers in COMBINATORICA
  • 1964-09. On extremal problems of graphs and generalized graphs in ISRAEL JOURNAL OF MATHEMATICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4296-0

    DOI

    http://dx.doi.org/10.1007/s00493-021-4296-0

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Birmingham, Birmingham, UK", 
              "id": "http://www.grid.ac/institutes/grid.6572.6", 
              "name": [
                "University of Birmingham, Birmingham, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Methuku", 
            "givenName": "Abhishek", 
            "id": "sg:person.012635672721.88", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012635672721.88"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "ETH Zurich, Zurich, Switzerland", 
              "id": "http://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "ETH Zurich, Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tomon", 
            "givenName": "Istv\u00e1n", 
            "id": "sg:person.012731525103.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012731525103.75"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02773960", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004551288", 
              "https://doi.org/10.1007/bf02773960"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02759942", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011160456", 
              "https://doi.org/10.1007/bf02759942"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01261323", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033310425", 
              "https://doi.org/10.1007/bf01261323"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01375476", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033659309", 
              "https://doi.org/10.1007/bf01375476"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-01-14", 
        "datePublishedReg": "2022-01-14", 
        "description": "A zero-one matrix M contains a zero-one matrix A if one can delete some rows and columns of M, and turn some 1-entries into 0-entries such that the resulting matrix is A. The extremal number of A, denoted by ex(n, A), is the maximum number of 1-entries in an n \u00d7 n sized matrix M that does not contain A.A matrix A is column-t-partite (or row-t-partite), if it can be cut along the columns (or rows) into t submatrices such that every row (or column) of these submatrices contains at most one 1-entry. We prove that if A is column-t-partite, then ex(nA)
     

    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/s00493-021-4296-0'

    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/s00493-021-4296-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4296-0'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4296-0'


     

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

    119 TRIPLES      21 PREDICATES      62 URIs      50 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4296-0 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N9507e3b7b6b145dd8ac6fab8e13bf85d
    4 schema:citation sg:pub.10.1007/bf01261323
    5 sg:pub.10.1007/bf01375476
    6 sg:pub.10.1007/bf02759942
    7 sg:pub.10.1007/bf02773960
    8 schema:datePublished 2022-01-14
    9 schema:datePublishedReg 2022-01-14
    10 schema:description A zero-one matrix M contains a zero-one matrix A if one can delete some rows and columns of M, and turn some 1-entries into 0-entries such that the resulting matrix is A. The extremal number of A, denoted by ex(n, A), is the maximum number of 1-entries in an n × n sized matrix M that does not contain A.A matrix A is column-t-partite (or row-t-partite), if it can be cut along the columns (or rows) into t submatrices such that every row (or column) of these submatrices contains at most one 1-entry. We prove that if A is column-t-partite, then ex(nA)<n2−1t+1t2+o(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm{ex}}(n,A) < {n^{2 - {1 \over t} + {1 \over {{t^2}}} + o(1)}}$$\end{document} and if A is both column- and row-t-partite, then ex(nA)<n2−1t+o(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm{ex}}(n,A) < {n^{2 - {1 \over t} + o(1)}}$$\end{document}. Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method.Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most t 1-entries in each row corresponds to a bipartite ordered graph with maximum degree t in one of its vertex classes. Our results are partially motivated by a well-known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if H is a bipartite graph with maximum degree t in one of the vertex classes, then ex(nH)=O(n2−1t)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm{ex}}(n,H) = O({n^{2 - {1 \over t}}})$$\end{document}. The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs.
    11 schema:genre article
    12 schema:isAccessibleForFree false
    13 schema:isPartOf sg:journal.1136493
    14 schema:keywords Alon
    15 Füredi
    16 Krivelevich
    17 Methuku
    18 Sudakov
    19 Turán number
    20 Turán problem
    21 aim
    22 argument
    23 bipartite
    24 bipartite graphs
    25 choice method
    26 class
    27 column
    28 degree t
    29 extremal number
    30 general results
    31 graph
    32 matrix
    33 matrix A
    34 matrix M
    35 maximum number
    36 method
    37 number
    38 paper
    39 present paper
    40 problem
    41 proof
    42 random choice method
    43 result of Füredi
    44 results
    45 rows
    46 similar general results
    47 submatrices
    48 type arguments
    49 vertex classes
    50 schema:name Bipartite Turán Problems for Ordered Graphs Abhishek Methuku, István Tomon
    51 schema:pagination 1-17
    52 schema:productId Nf996f1772530477abc3f1a8e0da47b6c
    53 Nfbe3918608524708bb0689fb03d4ce61
    54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1144707126
    55 https://doi.org/10.1007/s00493-021-4296-0
    56 schema:sdDatePublished 2022-10-01T06:49
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher N8973d956a1574bd08045d1886009757d
    59 schema:url https://doi.org/10.1007/s00493-021-4296-0
    60 sgo:license sg:explorer/license/
    61 sgo:sdDataset articles
    62 rdf:type schema:ScholarlyArticle
    63 N8973d956a1574bd08045d1886009757d schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 N9507e3b7b6b145dd8ac6fab8e13bf85d rdf:first sg:person.012635672721.88
    66 rdf:rest Nb794478c800344008e175a21c63ec9b9
    67 Nb794478c800344008e175a21c63ec9b9 rdf:first sg:person.012731525103.75
    68 rdf:rest rdf:nil
    69 Nf996f1772530477abc3f1a8e0da47b6c schema:name dimensions_id
    70 schema:value pub.1144707126
    71 rdf:type schema:PropertyValue
    72 Nfbe3918608524708bb0689fb03d4ce61 schema:name doi
    73 schema:value 10.1007/s00493-021-4296-0
    74 rdf:type schema:PropertyValue
    75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Mathematical Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Pure Mathematics
    80 rdf:type schema:DefinedTerm
    81 sg:grant.5239064 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4296-0
    82 rdf:type schema:MonetaryGrant
    83 sg:grant.7388353 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4296-0
    84 rdf:type schema:MonetaryGrant
    85 sg:grant.7747027 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4296-0
    86 rdf:type schema:MonetaryGrant
    87 sg:journal.1136493 schema:issn 0209-9683
    88 1439-6912
    89 schema:name Combinatorica
    90 schema:publisher Springer Nature
    91 rdf:type schema:Periodical
    92 sg:person.012635672721.88 schema:affiliation grid-institutes:grid.6572.6
    93 schema:familyName Methuku
    94 schema:givenName Abhishek
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012635672721.88
    96 rdf:type schema:Person
    97 sg:person.012731525103.75 schema:affiliation grid-institutes:grid.5801.c
    98 schema:familyName Tomon
    99 schema:givenName István
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012731525103.75
    101 rdf:type schema:Person
    102 sg:pub.10.1007/bf01261323 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033310425
    103 https://doi.org/10.1007/bf01261323
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/bf01375476 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033659309
    106 https://doi.org/10.1007/bf01375476
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/bf02759942 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011160456
    109 https://doi.org/10.1007/bf02759942
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/bf02773960 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004551288
    112 https://doi.org/10.1007/bf02773960
    113 rdf:type schema:CreativeWork
    114 grid-institutes:grid.5801.c schema:alternateName ETH Zurich, Zurich, Switzerland
    115 schema:name ETH Zurich, Zurich, Switzerland
    116 rdf:type schema:Organization
    117 grid-institutes:grid.6572.6 schema:alternateName University of Birmingham, Birmingham, UK
    118 schema:name University of Birmingham, Birmingham, UK
    119 rdf:type schema:Organization
     




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


    ...