Pasar al contenido principal

COMBINATORIA GEOMETRICA, ALGEBRAICA Y PROBABILISTICA

MTM2017-82166-P

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2017
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 12
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Set systems with distinct sumsets

  • Cilleruelo, Javier
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Wötzel, Maximilian|||0000-0001-7591-0998
A family $\mathcal{A}$ of $k$-subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+A'$, $A,A'\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$-subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=\Omega_k(N^{k-1})$. More precise bounds on $F_k(N)$ are obtained for $k\le 3$. We also obtain the threshold probability for a random system to be Sidon for $k= 2$ and $3$., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Weak components of the directed configuration model

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
The version of record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_109, We study the threshold for the existence of a linear order weakly connected component in the directed configuration model, confirming analytic but non-rigorous results recently obtained by Kryven [8]. We also establish convergence in probability of the fraction of vertices and edges that are contained in the largest component. As a consequence of our results, we obtain that the “separation” between the thresholds for the existence a giant weakly and strongly connected component is in some sense independent from the in-/out-degree correlation. We formalise this idea using bond percolation., G. Perarnau—Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017-82166-P and the MSCA-RISE-2020-101007705 - ‘RandNet’., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The rado multiplicity problem in vector spaces over finite fields

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Spiegel, Christoph
We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al.~\cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf~\cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov~\cite{razborov2007flag}., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Product-free sets in the free group

  • Ortega Sánchez Colomer, Miquel|||0009-0003-4043-7266
  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Serra Albó, Oriol|||0000-0001-8561-4631
We prove that product-free sets of the free group over a finite alphabet have max-imum density1/2with respect to the natural measure that assigns total weight oneto each set of irreducible words of a given length. This confirms a conjecture ofLeader, Letzter, Narayanan and Walters. In more general terms, we actually provethat stronglyk-product-free sets have maximum density1/kin terms of the saidmeasure. The bounds are tight., We acknowledge the support of the grants MTM2017-82166-P, PID2020-113082GB-I00,and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellencein R&D (CEX2020-001084-M). Miquel Ortega also acknowledges the support of the FPIgrant PRE2021-099120., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Extremal families for Kruskal-Katona Theorem

  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Vena Cros, Lluís|||0000-0002-0075-3673
Given a set of size $n$ and a positive integer $k<n$, Kruskal--Katona theorem gives the minimum size of the shadow of a family $S$ of $k$-sets of $[n]$ in terms of the cardinality of $S$. We give a characterization of the families of $k$-sets satisfying equality in Kruskal--Katona theorem. This answers a question of F\"uredi and Griggs., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Product-free sets in the free group

  • Ortega Sánchez Colomer, Miquel
  • Rué Perna, Juan José
  • Serra Albó, Oriol
We prove that product-free sets of the free group over a finite alphabet have max-imum density1/2with respect to the natural measure that assigns total weight oneto each set of irreducible words of a given length. This confirms a conjecture ofLeader, Letzter, Narayanan and Walters. In more general terms, we actually provethat stronglyk-product-free sets have maximum density1/kin terms of the saidmeasure. The bounds are tight., We acknowledge the support of the grants MTM2017-82166-P, PID2020-113082GB-I00,and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellencein R&D (CEX2020-001084-M). Miquel Ortega also acknowledges the support of the FPIgrant PRE2021-099120., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Weak components of the directed configuration model

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem
The version of record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_109, We study the threshold for the existence of a linear order weakly connected component in the directed configuration model, confirming analytic but non-rigorous results recently obtained by Kryven [8]. We also establish convergence in probability of the fraction of vertices and edges that are contained in the largest component. As a consequence of our results, we obtain that the “separation” between the thresholds for the existence a giant weakly and strongly connected component is in some sense independent from the in-/out-degree correlation. We formalise this idea using bond percolation., G. Perarnau—Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017-82166-P and the MSCA-RISE-2020-101007705 - ‘RandNet’., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

The rado multiplicity problem in vector spaces over finite fields

  • Rué Perna, Juan José
  • Spiegel, Christoph
We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al.~\cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf~\cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov~\cite{razborov2007flag}., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Extremal families for Kruskal-Katona Theorem

  • Serra Albó, Oriol
  • Vena Cros, Lluís
Given a set of size $n$ and a positive integer $k<n$, Kruskal--Katona theorem gives the minimum size of the shadow of a family $S$ of $k$-sets of $[n]$ in terms of the cardinality of $S$. We give a characterization of the families of $k$-sets satisfying equality in Kruskal--Katona theorem. This answers a question of F\"uredi and Griggs., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Set systems with distinct sumsets

  • Cilleruelo, Javier
  • Serra Albó, Oriol
  • Wötzel, Maximilian
A family $\mathcal{A}$ of $k$-subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+A'$, $A,A'\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$-subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=\Omega_k(N^{k-1})$. More precise bounds on $F_k(N)$ are obtained for $k\le 3$. We also obtain the threshold probability for a random system to be Sidon for $k= 2$ and $3$., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite graphs

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed, Postprint (author's final draft)