Pasar al contenido principal

COMBINATORIA: NUEVAS TENDENCIAS Y APLICACIONES

PID2020-113082GB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
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)

Polynomials for marked graphs and the chromatic symmetric function

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

On homogeneous matroid ports

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mier Vinué, Anna de|||0000-0002-2817-7807
A matroid port is a clutter (antichain of sets) determined by the collection of circuits of a matroid that contain a fixed point. We study the problem of determining matroid ports all whose elements have the same size h. This problem has been studied from the cryptographic perspective and it is related to an analogous problem in matroid theory. We give some general results and then focus on the binary case. We recast some known results and find all 4-homogeneous binary matroid ports., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Diner, Oznur Y.
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Serna Iglesias, María José|||0000-0001-9729-8648
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.
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)

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

Polynomials for marked graphs and the chromatic symmetric function

Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists., 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)

On homogeneous matroid ports

  • Martí Farré, Jaume
  • Mier Vinué, Anna de
A matroid port is a clutter (antichain of sets) determined by the collection of circuits of a matroid that contain a fixed point. We study the problem of determining matroid ports all whose elements have the same size h. This problem has been studied from the cryptographic perspective and it is related to an analogous problem in matroid theory. We give some general results and then focus on the binary case. We recast some known results and find all 4-homogeneous binary matroid ports., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep
  • Diner, Oznur Y.
  • Serra Albó, Oriol
  • Serna Iglesias, María José
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed, Postprint (published version)