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/bf01375476", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033659309", 
              "https://doi.org/10.1007/bf01375476"
            ], 
            "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"
          }
        ], 
        "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 N56ccc1f35da24a1a8bacd5ada609bb90
    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 N53a05826f48c4a82bc183cd25502c89a
    53 N92cbd433863443bcbfef1f26d8d0c632
    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-11-24T21:08
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher N3341b5c31be94b4285d7b5c3abbae204
    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 N3341b5c31be94b4285d7b5c3abbae204 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 N53a05826f48c4a82bc183cd25502c89a schema:name dimensions_id
    66 schema:value pub.1144707126
    67 rdf:type schema:PropertyValue
    68 N56ccc1f35da24a1a8bacd5ada609bb90 rdf:first sg:person.012635672721.88
    69 rdf:rest Nba163b302b7b47968e8d027cbe98552e
    70 N92cbd433863443bcbfef1f26d8d0c632 schema:name doi
    71 schema:value 10.1007/s00493-021-4296-0
    72 rdf:type schema:PropertyValue
    73 Nba163b302b7b47968e8d027cbe98552e rdf:first sg:person.012731525103.75
    74 rdf:rest rdf:nil
    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)


    ...