m
• D

F Nous contacter

0

Virtualconference

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

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

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

Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2228/Slides/talk_CAM2020_Montejano.pdf

 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 additiveOrganisateurs de la rencontre : Balandraud, Eric ; Dousse, Jehanne ; Girard, Benjamin ; Schmid, Wolfgang ; Tringali, SalvatoreDates : 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

Bibliographie

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. -

Z