F Nous contacter


H 1 Zero-sum squares in bounded discrepancy {-1,1}-matrices

Auteurs : Montejano, Amanda (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : A square in a matrix $\mathcal M =(a_{ij})$ is a 2X2 sub-matrix of $\mathcal M$ with entries $a_{ij}, a_{i+s,j}, ai,j+s, a_{i+s,j+s}$s for some $s\geq 1$. An Erickson matrix is a square binary matrix that contains no squares with constant entries. In [Eri96], Erickson asked for the maximum value of $n$ for which there exists an n x n Erickson matrix. In [AM08] Axenovich and Manske gave an upper bound of around $2^{2^{40}}$. This gargantuan bound was later improved by Bacher and Eliahou in [BE10] using computational means to the optimal value of 15.
    In this talk we present the study of a zero-sum analogue of the Erickson matrices problem where we consider binary matrices with entries in {-1,1}. For this purpose, of course, we need to take into account the discrepancy or deviation of the matrix, defined as the sum of all its entries, that is
    $disc(\mathcal M)= \sum_{1\leq i\leq n \; \; 1\leq j\leq m}a_{i,j}$.
    A zero-sum square is a square $\mathcal S$ with $disc(\mathcal S) = 0$. A natural question is, for example, the following: is it true that for sufficiently large $n$ every $n\times n \{-1,1\} - matrix \, \mathcal M$ with $disc(\mathcal M) = 0$ contains a zero-sum square? We answered positive to this question. Since, our proof uses an induction argument, in order for the induction to work we prove the following stronger statement: For $n \geq 5$ and $m \in \{n,n+1\}$, every $ n \times m \{-1, 1\}$ -matrix $M$ with $\left | disc(M) \right |\leq n$ contains a zero-sum square except for the triangular matrix (up to symmetries), where a triangular matrix is a matrix with all entries above the diagonal equal to -1 and all remaining entries equal to 1.This is a joint work with Edgardo Roldn-Pensado and Alma R. Arvalo.

    Keywords : zero-sum Ramsey theory; discrepancy theory; binary matrices

    Codes MSC :
    05C55 - Generalized Ramsey theory
    05D05 - Extremal set theory
    11P99 - None of the above but in this section

    Ressources complémentaires :

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 29/09/2020
      Date de captation : 08/09/2020
      Collection : Research talks ; Number Theory ; Combinatorics
      Durée : 00:35:03
      Domaine : Number Theory ; Combinatorics
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2020-09-08_Montejano.mp4

    Informations sur la Rencontre Virtuelle

    Nom de la rencontre : Additive Combinatorics / Combinatoire additive
    Organisateurs de la rencontre : Balandraud, Eric ; Dousse, Jehanne ; Girard, Benjamin ; Schmid, Wolfgang ; Tringali, Salvatore
    Dates : 07/09/2020 - 11/09/2020
    Année de la rencontre : 2020
    URL Congrès : https://conferences.cirm-math.fr/2228.html

    Citation Data

    DOI : 10.24350/CIRM.V.19654003
    Cite this video as: Montejano, Amanda (2020). Zero-sum squares in bounded discrepancy {-1,1}-matrices.CIRM . Audiovisual resource. doi:10.24350/CIRM.V.19654003
    URI : http://dx.doi.org/10.24350/CIRM.V.19654003

    Voir aussi


    1. [ARM20] A. R. Arvalo, A. Montejano and E. Roldn-Pensado, Zero-sum squares in bounded discrepancy {-1; 1}-matrices, arXiv:2005.07813 (2020). - https://arxiv.org/abs/2005.07813

    2. [AM08] M. Axenovich and J. Manske, On monochromatic subsets of a rectangular grid, Integers 8 (2008), A21, 14. - http://math.colgate.edu/~integers/i21/i21.pdf

    3. [BE10] R. Bacher and S. Eliahou, Extremal binary matrices without constant 2-squares, J. Comb.1 (2010), no. 1, 77{100. - http://dx.doi.org/10.4310/JOC.2010.v1.n1.a6

    4. [Eri96] M. J. Erickson, Introduction to combinatorics, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1996, A Wiley-Interscience Publication. -