-
Graph Reconstruction with Connectivity Queries
Authors:
Kacper Kluk,
Hoang La,
Marta Piecyk
Abstract:
We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2023) for triples ($k=3$), this problem received comprehensive attention in their work, alongside a study by Qi, who provided a complete characterization of graphs uniquely reconstructible via their connected triples, i.e…
▽ More
We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2023) for triples ($k=3$), this problem received comprehensive attention in their work, alongside a study by Qi, who provided a complete characterization of graphs uniquely reconstructible via their connected triples, i.e. no other graphs share the same set of connected triples. Our contribution consists in output-polynomial time algorithms that enumerate every triangle-free graph (resp. every graph with bounded maximum degree) that is consistent with a specified set of connected $k$-sets. Notably, we prove that triangle-free graphs are uniquely reconstructible, while graphs with bounded maximum degree that are consistent with the same $k$-sets share a substantial common structure, differing only locally. We suspect that the problem is NP-hard in general and provide a NP-hardness proof for a variant where the connectivity is specified for only some $k$-sets (with $k$ at least 4).
△ Less
Submitted 10 July, 2024;
originally announced July 2024.
-
Weak coloring numbers of minor-closed graph classes
Authors:
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Clément Rambaud
Abstract:
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $\mathcal{O}(r \log r)$. Moreover, we tie the exponent of the polynomial to…
▽ More
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $\mathcal{O}(r \log r)$. Moreover, we tie the exponent of the polynomial to a structural property of $X$, namely, $2$-treedepth. As a result, for a fixed graph $X$ and an $X$-minor-free graph $G$, we show that $\mathrm{wcol}_r(G)= \mathcal{O}(r^{\mathrm{td}(X)-1}\mathrm{log}\ r)$, which improves on the bound $\mathrm{wcol}_r(G) = \mathcal{O}(r^{g(\mathrm{td}(X))})$ given by Dujmović et al. (SODA, 2024), where $g$ is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum $r$-th weak coloring number is in $\mathcal{O}(r^2\mathrm{log}\ r$), which is best possible.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Guarding isometric subgraphs and Cops and Robber in planar graphs
Authors:
Sebastián González Hermosillo de la Maza,
Bojan Mohar
Abstract:
In the game of Cops and Robbers, one of the most useful results is that an isometric path in a graph can be guarded by one cop. In this paper, we introduce the concept of wide shadow in a subgraph, and use it to characterize all 1-guardable graphs. As an application, we show that 3 cops can capture a robber in any planar graph with the added restriction that at most two cops can move simultaneousl…
▽ More
In the game of Cops and Robbers, one of the most useful results is that an isometric path in a graph can be guarded by one cop. In this paper, we introduce the concept of wide shadow in a subgraph, and use it to characterize all 1-guardable graphs. As an application, we show that 3 cops can capture a robber in any planar graph with the added restriction that at most two cops can move simultaneously, proving a conjecture of Yang and strengthening a classical result of Aigner and Fromme.
△ Less
Submitted 3 June, 2024;
originally announced June 2024.
-
Quickly excluding an apex-forest
Authors:
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Clément Rambaud
Abstract:
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treed…
▽ More
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs.
△ Less
Submitted 26 April, 2024;
originally announced April 2024.
-
The $χ$-binding function of $d$-directional segment graphs
Authors:
Lech Duraj,
Ross J. Kang,
Hoang La,
Jonathan Narboni,
Filip Pokrývka,
Clément Rambaud,
Amadeus Reinald
Abstract:
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $ω$ that the chromatic number $χ(G)$ of $G$ is at most $dω$. We show for every even value of $ω$ ho…
▽ More
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $ω$ that the chromatic number $χ(G)$ of $G$ is at most $dω$. We show for every even value of $ω$ how to construct a graph in $d$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $χ$-binding function of $d$-DIR is $ω\mapsto dω$ for $ω$ even and $ω\mapsto d(ω-1)+1$ for $ω$ odd. This refutes said conjecture of Bhattacharya, Dvořák and Noorizadeh.
△ Less
Submitted 12 September, 2023;
originally announced September 2023.
-
Boolean dimension of a Boolean lattice
Authors:
Marcin Briański,
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Katzper Michno
Abstract:
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
△ Less
Submitted 31 July, 2023;
originally announced July 2023.
-
The grid-minor theorem revisited
Authors:
Vida Dujmović,
Robert Hickingbotham,
Jędrzej Hodor,
Gweanël Joret,
Hoang La,
Piotr Micek,
Pat Morin,
Clément Rambaud,
David R. Wood
Abstract:
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in s…
▽ More
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a fixed graph as a minor.
△ Less
Submitted 6 July, 2023;
originally announced July 2023.
-
$2$-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
Authors:
Hoang La,
Kenny Štorgel
Abstract:
In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely $2$-distance coloring, injective coloring, and exact square coloring. A $2$-distance coloring is a proper coloring of the vertices in which no two vertices at distance $2$ receive the same color, an injective coloring is a coloring of the vertices in which no two vertices with…
▽ More
In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely $2$-distance coloring, injective coloring, and exact square coloring. A $2$-distance coloring is a proper coloring of the vertices in which no two vertices at distance $2$ receive the same color, an injective coloring is a coloring of the vertices in which no two vertices with a common neighbor receive the same color, and an exact square coloring is a coloring of the vertices in which no two vertices at distance exactly $2$ receive the same color. We prove that planar graphs with maximum degree $Δ= 4$ and girth at least $4$ are $2$-distance list $(Δ+ 7)$-colorable and injectively list $(Δ+ 5)$-colorable. Additionally, we prove that planar graphs with $Δ= 4$ are injectively list $(Δ+ 7)$-colorable and exact square list $(Δ+ 6)$-colorable.
△ Less
Submitted 16 May, 2022;
originally announced May 2022.
-
Computer assisted discharging procedure on planar graphs: application to 2-distance coloring
Authors:
Hoang La,
Petru Valicov
Abstract:
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques to study the 2-distance coloring of planar subcubic graphs. Applying these techniques we show that every subcubic planar graph $G$ of girth at least 8 has 2-distance chromatic number at most 6.
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques to study the 2-distance coloring of planar subcubic graphs. Applying these techniques we show that every subcubic planar graph $G$ of girth at least 8 has 2-distance chromatic number at most 6.
△ Less
Submitted 13 February, 2022; v1 submitted 8 February, 2022;
originally announced February 2022.
-
Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
Authors:
Kolja Knauer,
Hoang La,
Petru Valicov
Abstract:
We study the minimum size $f$ of a feedback vertex set in directed and undirected $n$-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\frac{k-1}{k+1}n$ is known to be tight for graphs with bounded treewidth $k$ or bounded odd degeneracy $k$. We show that neither of the easy upper and lower bounds $\frac{k-1}{k+1}n$ and $\frac{k}{k+2}n$ can be exact for the case…
▽ More
We study the minimum size $f$ of a feedback vertex set in directed and undirected $n$-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\frac{k-1}{k+1}n$ is known to be tight for graphs with bounded treewidth $k$ or bounded odd degeneracy $k$. We show that neither of the easy upper and lower bounds $\frac{k-1}{k+1}n$ and $\frac{k}{k+2}n$ can be exact for the case of even degeneracy. More precisely, for even degeneracy $k$ we prove that $f < \frac{k}{k+2}n$ and for every $ε>0$, there exists a $k$-degenerate graph for which $f\geq \frac{3k-2}{3k+4}n -ε$.
For directed graphs of bounded degeneracy $k$, we prove that $f\leq\frac{k-1}{k+1}n$ and that this inequality is strict when $k$ is odd. For directed graphs of bounded treewidth $k\geq 2$, we show that $f \leq \frac{k}{k+3}n$ and for every $ε>0$, there exists a $k$-degenerate graph for which $f\geq \frac{k-2\lfloor\log_2(k)\rfloor}{k+1}n -ε$. Further, we provide several constructions of low degeneracy or treewidth and large $f$.
△ Less
Submitted 13 July, 2022; v1 submitted 29 November, 2021;
originally announced November 2021.
-
Further Extensions of the Grötzsch Theorem
Authors:
Hoang La,
Borut Lužar,
Kenny Štorgel
Abstract:
The Grötzsch Theorem states that every triangle-free planar graph admits a proper $3$-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving $3$-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending $3$-colorings of subgraphs to the whole graph. In this paper, we consider $3$-colorings of…
▽ More
The Grötzsch Theorem states that every triangle-free planar graph admits a proper $3$-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving $3$-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending $3$-colorings of subgraphs to the whole graph. In this paper, we consider $3$-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most $4$ can be extended to a $3$-coloring of the graph. Additionally, we show that for every vertex of degree at most $3$, a precoloring of its neighborhood with the same color extends to a $3$-coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.
△ Less
Submitted 5 October, 2021;
originally announced October 2021.
-
$2$-distance list $(Δ+2)$-coloring of planar graphs with girth at least 10
Authors:
Hoang La,
Mickael Montassier
Abstract:
Given a graph $G$ and a list assignment $L(v)$ for each vertex of $v$ of $G$. A proper $L$-list-coloring of $G$ is a function that maps every vertex to a color in $L(v)$ such that no pair of adjacent vertices have the same color. We say that a graph is list $k$-colorable when every vertex $v$ has a list of colors of size at least $k$. A $2$-distance coloring is a coloring where vertices at distanc…
▽ More
Given a graph $G$ and a list assignment $L(v)$ for each vertex of $v$ of $G$. A proper $L$-list-coloring of $G$ is a function that maps every vertex to a color in $L(v)$ such that no pair of adjacent vertices have the same color. We say that a graph is list $k$-colorable when every vertex $v$ has a list of colors of size at least $k$. A $2$-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance list ($Δ+2$)-coloring for planar graphs with girth at least $10$ and maximum degree $Δ\geq 4$.
△ Less
Submitted 29 September, 2021;
originally announced September 2021.
-
$2$-distance $(Δ+2)$-coloring of sparse graphs
Authors:
Hoang La,
Mickael Montassier
Abstract:
A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($Δ+2$)-coloring for graphs with maximum average degree less than $\frac{8}{3}$ (resp. $\frac{14}{5}$) and maximum degree $Δ\geq 6$ (resp. $Δ\geq 10$). As a corollary, every planar graph with girth at least $8$ (r…
▽ More
A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($Δ+2$)-coloring for graphs with maximum average degree less than $\frac{8}{3}$ (resp. $\frac{14}{5}$) and maximum degree $Δ\geq 6$ (resp. $Δ\geq 10$). As a corollary, every planar graph with girth at least $8$ (resp. $7$) and maximum degree $Δ\geq 6$ (resp. $Δ\geq 10$) admits a $2$-distance $(Δ+2)$-coloring.
△ Less
Submitted 24 September, 2021;
originally announced September 2021.
-
2-distance 4-coloring of planar subcubic graphs with girth at least 21
Authors:
Hoang La,
Mickael Montassier
Abstract:
A $2$-distance $k$-coloring of a graph is a proper vertex $k$-coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance $4$-coloring for planar subcubic graphs with girth at least 21. We also show a construction of a planar subcubic graph of girth 11 that is not $2$-distance $4$-colorable.
A $2$-distance $k$-coloring of a graph is a proper vertex $k$-coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance $4$-coloring for planar subcubic graphs with girth at least 21. We also show a construction of a planar subcubic graph of girth 11 that is not $2$-distance $4$-colorable.
△ Less
Submitted 7 June, 2024; v1 submitted 7 June, 2021;
originally announced June 2021.
-
2-distance list $(Δ+ 3)$-coloring of sparse graphs
Authors:
Hoang La
Abstract:
A 2-distance list k-coloring of a graph is a proper coloring of the vertices where each vertex has a list of at least k available colors and vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list $(Δ+ 3)$-coloring for graphs with maximum average degree less than $\frac83$ and maximum degree $Δ\geq 4$ as well as graphs with maximum average degree les…
▽ More
A 2-distance list k-coloring of a graph is a proper coloring of the vertices where each vertex has a list of at least k available colors and vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list $(Δ+ 3)$-coloring for graphs with maximum average degree less than $\frac83$ and maximum degree $Δ\geq 4$ as well as graphs with maximum average degree less than $\frac{14}5$ and maximum degree $Δ\geq 6$.
△ Less
Submitted 4 May, 2021;
originally announced May 2021.
-
$2$-distance $(Δ+1)$-coloring of sparse graphs using the potential method
Authors:
Hoang La,
Mickael Montassier
Abstract:
A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($Δ+1$)-coloring for graphs with maximum average degree less than $\frac{18}{7}$ and maximum degree $Δ\geq 7$. As a corollary, every planar graph with girth at least $9$ and $Δ\geq 7$ admits a $2$-distance…
▽ More
A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($Δ+1$)-coloring for graphs with maximum average degree less than $\frac{18}{7}$ and maximum degree $Δ\geq 7$. As a corollary, every planar graph with girth at least $9$ and $Δ\geq 7$ admits a $2$-distance $(Δ+1)$-coloring. The proof uses the potential method to reduce new configurations compared to classic approaches on $2$-distance coloring.
△ Less
Submitted 3 April, 2021; v1 submitted 22 March, 2021;
originally announced March 2021.
-
A note on deterministic zombies
Authors:
Valentin Bartier,
Laurine Bénéteau,
Marthe Bonamy,
Hoang La,
Jonathan Narboni
Abstract:
"Zombies and Survivor" is a variant of the well-studied game of "Cops and Robber" where the zombies (cops) can only move closer to the survivor (robber). We consider the deterministic version of the game where a zombie can choose their path if multiple options are available. The zombie number, like the cop number, of a graph is the minimum number of zombies, or cops, required to capture the surviv…
▽ More
"Zombies and Survivor" is a variant of the well-studied game of "Cops and Robber" where the zombies (cops) can only move closer to the survivor (robber). We consider the deterministic version of the game where a zombie can choose their path if multiple options are available. The zombie number, like the cop number, of a graph is the minimum number of zombies, or cops, required to capture the survivor. In this short note, we solve a question by Fitzpatrick et al., proving that the zombie number of the Cartesian product of two graphs is at most the sum of their zombie numbers. We also give a simple graph family with cop number $2$ and an arbitrarily large zombie number.
△ Less
Submitted 3 June, 2021; v1 submitted 8 August, 2020;
originally announced August 2020.
-
Sharp Concentration Results for Heavy-Tailed Distributions
Authors:
Milad Bakhshizadeh,
Arian Maleki,
Victor H. de la Pena
Abstract:
We obtain concentration and large deviation for the sums of independent and identically distributed random variables with heavy-tailed distributions. Our concentration results are concerned with random variables whose distributions satisfy $\mathbb{P}(X>t) \leq {\rm e}^{- I(t)}$, where $I: \mathbb{R} \rightarrow \mathbb{R}$ is an increasing function and $I(t)/t \rightarrow α\in [0, \infty)$ as…
▽ More
We obtain concentration and large deviation for the sums of independent and identically distributed random variables with heavy-tailed distributions. Our concentration results are concerned with random variables whose distributions satisfy $\mathbb{P}(X>t) \leq {\rm e}^{- I(t)}$, where $I: \mathbb{R} \rightarrow \mathbb{R}$ is an increasing function and $I(t)/t \rightarrow α\in [0, \infty)$ as $t \rightarrow \infty$. Our main theorem can not only recover some of the existing results, such as the concentration of the sum of subWeibull random variables, but it can also produce new results for the sum of random variables with heavier tails. We show that the concentration inequalities we obtain are sharp enough to offer large deviation results for the sums of independent random variables as well. Our analyses which are based on standard truncation arguments simplify, unify and generalize the existing results on the concentration and large deviation of heavy-tailed random variables.
△ Less
Submitted 25 July, 2022; v1 submitted 30 March, 2020;
originally announced March 2020.
-
Meyniel's conjecture on graphs of bounded degree
Authors:
Seyyed Aliasghar Hosseini,
Bojan Mohar,
Sebastian Gonzalez Hermosillo de la Maza
Abstract:
The game of Cops and Robbers is a well known pursuit-evasion game played on graphs. It has been proved \cite{bounded_degree} that cubic graphs can have arbitrarily large cop number $c(G)$, but the known constructions show only that the set $\{c(G) \mid G \text{ cubic}\}$ is unbounded. In this paper we prove that there are arbitrarily large subcubic graphs $G$ whose cop number is at least…
▽ More
The game of Cops and Robbers is a well known pursuit-evasion game played on graphs. It has been proved \cite{bounded_degree} that cubic graphs can have arbitrarily large cop number $c(G)$, but the known constructions show only that the set $\{c(G) \mid G \text{ cubic}\}$ is unbounded. In this paper we prove that there are arbitrarily large subcubic graphs $G$ whose cop number is at least $n^{1/2-o(1)}$ where $n=|V(G)|$. We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weak Meyniel's conjecture for all graphs.
△ Less
Submitted 20 November, 2020; v1 submitted 14 December, 2019;
originally announced December 2019.
-
Vertex arboricity of cographs
Authors:
Sebastián González Hermosillo de la Maza,
Pavol Hell,
César Hernández Cruz,
Seyyed Aliasghar Hosseini,
Payam Valadkhan
Abstract:
Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of…
▽ More
Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity. We obtain bounds on their size and the height of their cotrees.
More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers $p$ and $q$, we ask if a given cograph $G$ admits a vertex partition into $p$ forests and $q$ independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum $q$-colourable subgraph, maximum subgraph of arboricity-$p$, minimum vertex feedback set and minimum $q$ of a $q$-colourable vertex feedback set.
△ Less
Submitted 16 July, 2019;
originally announced July 2019.
-
Cops and robbers on oriented toroidal grids
Authors:
Sebastian Gonzalez Hermosillo de la Maza,
Seyyed Aliasghar Hosseini,
Fiachra Knox,
Bojan Mohar,
Bruce Reed
Abstract:
The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.
The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.
△ Less
Submitted 11 May, 2020; v1 submitted 22 April, 2019;
originally announced April 2019.
-
On the structure of (claw,bull)-free graphs
Authors:
Sebastián González Hermosillo de la Maza,
Yifan Jing,
Masood Masjoody
Abstract:
In this research, we determine the structure of (claw, bull)-free graphs. We show that every connected (claw, bull)-free graph is either an expansion of a path, an expansion of a cycle, or the complement of a triangle-free graph; where an expansion of a graph $G$ is obtained by replacing its vertices with disjoint cliques and adding all edges between cliques corresponding to adjacent vertices of…
▽ More
In this research, we determine the structure of (claw, bull)-free graphs. We show that every connected (claw, bull)-free graph is either an expansion of a path, an expansion of a cycle, or the complement of a triangle-free graph; where an expansion of a graph $G$ is obtained by replacing its vertices with disjoint cliques and adding all edges between cliques corresponding to adjacent vertices of $G$. This result also reveals facts about the structure of triangle-free graphs, which might be of independent interest.
△ Less
Submitted 31 December, 2018;
originally announced January 2019.
-
A rainbow version of Mantel's Theorem
Authors:
Ron Aharoni,
Matt DeVos,
Sebastián González Hermosillo de la Maza,
Amanda Montejano,
Robert Šámal
Abstract:
Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist disti…
▽ More
Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$. We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi. We include a new short proof of Mantel's Theorem we obtained as a byproduct.
△ Less
Submitted 25 February, 2020; v1 submitted 31 December, 2018;
originally announced December 2018.
-
Short rainbow cycles in graphs and matroids
Authors:
Matt DeVos,
Matthew Drescher,
Daryl Funk,
Sebastián González Hermosillo de la Maza,
Krystal Guo,
Tony Huynh,
Bojan Mohar,
Amanda Montejano
Abstract:
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $\lceil \frac{n}{2} \rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generaliza…
▽ More
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $\lceil \frac{n}{2} \rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
△ Less
Submitted 7 May, 2020; v1 submitted 3 June, 2018;
originally announced June 2018.
-
The infinitely many zeros of stochastic coupled oscillators driven by random forces
Authors:
H. de la Cruz,
J. C. Jimenez,
R. J. Biscay
Abstract:
In this work, previous results concerning the infinitely many zeros of single stochastic oscillators driven by random forces are extended to the general class of coupled stochastic oscillators. We focus on three main subjects: 1) the analysis of this oscillatory behavior for the case of coupled harmonic oscillators; 2) the identification of some classes of coupled nonlinear oscillators showing thi…
▽ More
In this work, previous results concerning the infinitely many zeros of single stochastic oscillators driven by random forces are extended to the general class of coupled stochastic oscillators. We focus on three main subjects: 1) the analysis of this oscillatory behavior for the case of coupled harmonic oscillators; 2) the identification of some classes of coupled nonlinear oscillators showing this oscillatory dynamics and 3) the capability of some numerical integrators - thought as discrete dynamical systems - for reproducing the infinitely many zeros of coupled harmonic oscillators driven by random forces.
△ Less
Submitted 16 May, 2017;
originally announced May 2017.
-
On the existence of $3$- and $4$-kernels in digraphs
Authors:
Sebastián González Hermosillo de la Maza,
César Hernández-Cruz
Abstract:
Let $D = (V(D), A(D))$ be a digraph. A subset $S \subseteq V(D)$ is $k$-independent if the distance between every pair of vertices of $S$ is at least $k$, and it is $\ell$-absorbent if for every vertex $u$ in $V(D) \setminus S$ there exists $v \in S$ such that the distance from $u$ to $v$ is less than or equal to $\ell$. A $k$-kernel is a $k$-independent and $(k-1)$-absorbent set. A kernel is simp…
▽ More
Let $D = (V(D), A(D))$ be a digraph. A subset $S \subseteq V(D)$ is $k$-independent if the distance between every pair of vertices of $S$ is at least $k$, and it is $\ell$-absorbent if for every vertex $u$ in $V(D) \setminus S$ there exists $v \in S$ such that the distance from $u$ to $v$ is less than or equal to $\ell$. A $k$-kernel is a $k$-independent and $(k-1)$-absorbent set. A kernel is simply a $2$-kernel.
A classical result due to Duchet states that if every directed cycle in a digraph $D$ has at least one symmetric arc, then $D$ has a kernel. We propose a conjecture generalizing this result for $k$-kernels and prove it true for $k = 3$ and $k = 4$.
△ Less
Submitted 18 October, 2016;
originally announced October 2016.
-
Proper Orientations of Planar Bipartite Graphs
Authors:
Fiachra Knox,
Sebastián González Hermosillo de la Maza,
Bojan Mohar,
Cláudia Linhares Sales
Abstract:
An orientation of a graph $G$ is proper if any two adjacent vertices have different indegrees. The proper orientation number $\overrightarrowχ(G)$ of a graph $G$ is the minimum of the maximum indegree, taken over all proper orientations of $G$. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set o…
▽ More
An orientation of a graph $G$ is proper if any two adjacent vertices have different indegrees. The proper orientation number $\overrightarrowχ(G)$ of a graph $G$ is the minimum of the maximum indegree, taken over all proper orientations of $G$. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that $\overrightarrowχ(G) \leq 4$, when $G$ is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.
△ Less
Submitted 21 September, 2016;
originally announced September 2016.
-
Asymptotics for cuspidal representations by functoriality from GL(2)
Authors:
Huixue Lao,
Mark McKee,
Yangbo Ye
Abstract:
Let $π$ be a unitary automorphic cuspidal representation of $GL_2(\mathbb{Q}_\mathbb{A})$ with Fourier coefficients $λ_π(n)$. Asymptotic expansions of certain sums of $λ_π(n)$ are proved using known functorial liftings from $GL_2$, including symmetric powers, isobaric sums, exterior square from $GL_4$ and base change. These asymptotic expansions are manifestation of the underlying functoriality an…
▽ More
Let $π$ be a unitary automorphic cuspidal representation of $GL_2(\mathbb{Q}_\mathbb{A})$ with Fourier coefficients $λ_π(n)$. Asymptotic expansions of certain sums of $λ_π(n)$ are proved using known functorial liftings from $GL_2$, including symmetric powers, isobaric sums, exterior square from $GL_4$ and base change. These asymptotic expansions are manifestation of the underlying functoriality and reflect value distribution of $λ_π(n)$ on integers, squares, cubes and fourth powers.
△ Less
Submitted 5 October, 2015;
originally announced October 2015.
-
Graph 4-braid groups and Massey products
Authors:
Ki Hyoung Ko,
Joon Hyun La,
Hyo Won Park
Abstract:
We first show that the braid group over a graph topologically containing no $Θ$-shape subgraph has a presentation related only by commutators. Then using discrete Morse theory and triple Massey products, we prove that a graph topologically contains none of four prescribed graphs if and only if its 4-braid groups is a right-angled Artin group.
We first show that the braid group over a graph topologically containing no $Θ$-shape subgraph has a presentation related only by commutators. Then using discrete Morse theory and triple Massey products, we prove that a graph topologically contains none of four prescribed graphs if and only if its 4-braid groups is a right-angled Artin group.
△ Less
Submitted 14 July, 2014;
originally announced July 2014.
-
Local Linearization-Runge Kutta Methods: a class of A-stable explicit integrators for dynamical systems
Authors:
H. de la Cruz,
R. J. Biscay,
J. C. Jimenez,
F. Carbonell
Abstract:
A new approach for the construction of high order A-stable explicit integrators for ordinary differential equations (ODEs) is theoretically studied. Basically, the integrators are obtained by splitting, at each time step, the solution of the original equation in two parts: the solution of a linear ordinary differential equation plus the solution of an auxiliary ODE. The first one is solved by a Lo…
▽ More
A new approach for the construction of high order A-stable explicit integrators for ordinary differential equations (ODEs) is theoretically studied. Basically, the integrators are obtained by splitting, at each time step, the solution of the original equation in two parts: the solution of a linear ordinary differential equation plus the solution of an auxiliary ODE. The first one is solved by a Local Linearization scheme in such a way that A-stability is ensured, while the second one can be approximated by any extant scheme, preferably a high order explicit Runge-Kutta scheme. Results on the convergence and dynamical properties of this new class of schemes are given, as well as some hints for their efficient numerical implementation. An specific scheme of this new class is derived in detail, and its performance is compared with some Matlab codes in the integration of a variety of ODEs representing different types of dynamics.
△ Less
Submitted 25 July, 2012;
originally announced August 2012.
-
Pseudo-maximization and self-normalized processes
Authors:
Victor H. de la Peña,
Michael J. Klass,
Tze Leung Lai
Abstract:
Self-normalized processes are basic to many probabilistic and statistical studies. They arise naturally in the the study of stochastic integrals, martingale inequalities and limit theorems, likelihood-based methods in hypothesis testing and parameter estimation, and Studentized pivots and bootstrap-$t$ methods for confidence intervals. In contrast to standard normalization, large values of the o…
▽ More
Self-normalized processes are basic to many probabilistic and statistical studies. They arise naturally in the the study of stochastic integrals, martingale inequalities and limit theorems, likelihood-based methods in hypothesis testing and parameter estimation, and Studentized pivots and bootstrap-$t$ methods for confidence intervals. In contrast to standard normalization, large values of the observations play a lesser role as they appear both in the numerator and its self-normalized denominator, thereby making the process scale invariant and contributing to its robustness. Herein we survey a number of results for self-normalized processes in the case of dependent variables and describe a key method called ``pseudo-maximization'' that has been used to derive these results. In the multivariate case, self-normalization consists of multiplying by the inverse of a positive definite matrix (instead of dividing by a positive random variable as in the scalar case) and is ubiquitous in statistical applications, examples of which are given.
△ Less
Submitted 10 October, 2007; v1 submitted 14 September, 2007;
originally announced September 2007.
-
Characterizations of joint distributions, copulas, information, dependence and decoupling, with applications to time series
Authors:
Victor H. de la Peña,
Rustam Ibragimov,
Shaturgun Sharakhmetov
Abstract:
In this paper, we obtain general representations for the joint distributions and copulas of arbitrary dependent random variables absolutely continuous with respect to the product of given one-dimensional marginal distributions. The characterizations obtained in the paper represent joint distributions of dependent random variables and their copulas as sums of $U$-statistics in independent random…
▽ More
In this paper, we obtain general representations for the joint distributions and copulas of arbitrary dependent random variables absolutely continuous with respect to the product of given one-dimensional marginal distributions. The characterizations obtained in the paper represent joint distributions of dependent random variables and their copulas as sums of $U$-statistics in independent random variables. We show that similar results also hold for expectations of arbitrary statistics in dependent random variables. As a corollary of the results, we obtain new representations for multivariate divergence measures as well as complete characterizations of important classes of dependent random variables that give, in particular, methods for constructing new copulas and modeling different dependence structures. The results obtained in the paper provide a device for reducing the analysis of convergence in distribution of a sum of a double array of dependent random variables to the study of weak convergence for a double array of their independent copies. Weak convergence in the dependent case is implied by similar asymptotic results under independence together with convergence to zero of one of a series of dependence measures including the multivariate extension of Pearson's correlation, the relative entropy or other multivariate divergence measures. A closely related result involves conditions for convergence in distribution of $m$-dimensional statistics $h(X_t,X_{t+1},...,X_{t+m-1})$ of time series $\{X_t\}$ in terms of weak convergence of $h(ξ_t,ξ_{t+1},...,ξ_{t+m-1})$, where $\{ξ_t\}$ is a sequence of independent copies of $X_t'$s, and convergence to zero of measures of intertemporal dependence in $\{X_t\}$. The tools used include new sharp estimates for the distance between the distribution function of an arbitrary statistic in dependent random variables and the distribution function of the statistic in independent copies of the random variables in terms of the measures of dependence of the random variables. Furthermore, we obtain new sharp complete decoupling moment and probability inequalities for dependent random variables in terms of their dependence characteristics.
△ Less
Submitted 7 November, 2006;
originally announced November 2006.
-
Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
Authors:
Victor H. de la Pena,
Michael J. Klass,
Tze Leung Lai
Abstract:
Self-normalized processes arise naturally in statistical applications.
Being unit free, they are not affected by scale changes. Moreover, self-normalization often eliminates or weakens moment assumptions. In this paper we present several exponential and moment inequalities, particularly those related to laws of the iterated logarithm, for self-normalized random variables including martingales.…
▽ More
Self-normalized processes arise naturally in statistical applications.
Being unit free, they are not affected by scale changes. Moreover, self-normalization often eliminates or weakens moment assumptions. In this paper we present several exponential and moment inequalities, particularly those related to laws of the iterated logarithm, for self-normalized random variables including martingales. Tail probability bounds are also derived. For random variables B_t>0 and A_t, let Y_t(λ)=\exp{λA_t-λ^2B_t^2/2}. We develop inequalities for the moments of A_t/B_{t} or sup_{t\geq 0}A_t/{B_t(\log \log B_{t})^{1/2}} and variants thereof, when EY_t(λ)\leq 1 or when Y_t(λ) is a supermartingale, for all λbelonging to some interval. Our results are valid for a wide class of random processes including continuous martingales with A_t=M_t and B_t=\sqrt < M>_t, and sums of conditionally symmetric variables d_i with A_t=\sum_{i=1}^td_i and B_t=\sqrt\sum_{i=1}^td_i^2. A sharp maximal inequality for conditionally symmetric random variables and for continuous local martingales with values in R^m, m\ge 1, is also established. Another development in this paper is a bounded law of the iterated logarithm for general adapted sequences that are centered at certain truncated conditional expectations and self-normalized by the square root of the sum of squares. The key ingredient in this development is a new exponential supermartingale involving \sum_{i=1}^td_i and \sum_{i=1}^td_i^2.
△ Less
Submitted 5 October, 2004;
originally announced October 2004.
-
Decoupling Inequalities for the Tail Probabilities of Multivariate U-statistics
Authors:
Victor H. de la Peña,
Stephen J. Montgomery-Smith
Abstract:
In this paper the following result, which allows one to decouple U-Statistics in tail probability, is proved in full generality.
Theorem 1. Let $X_i$ be a sequence of independent random variables taking values in a measure space $S$, and let $f_{i_1...i_k}$ be measurable functions from $S^k$ to a Banach space $B$. Let $(X_i^{(j)})$ be independent copies of $(X_i)$. The following inequality hol…
▽ More
In this paper the following result, which allows one to decouple U-Statistics in tail probability, is proved in full generality.
Theorem 1. Let $X_i$ be a sequence of independent random variables taking values in a measure space $S$, and let $f_{i_1...i_k}$ be measurable functions from $S^k$ to a Banach space $B$. Let $(X_i^{(j)})$ be independent copies of $(X_i)$. The following inequality holds for all $t \ge 0$ and all $n\ge 2$, $$ P(||\sum_{1\le i_1 \ne ... \ne i_k \le n} f_{i_1 ... i_k}(X_{i_1},...,X_{i_k}) || \ge t) \qquad\qquad$$ $$ \qquad\qquad\le C_k P(C_k||\sum_{1\le i_1 \ne ... \ne i_k \le n} f_{i_1 ... i_k}(X_{i_1}^{(1)},...,X_{i_k}^{(k)}) || \ge t) .$$ Furthermore, the reverse inequality also holds in the case that the functions $\{f_{i_1... i_k}\}$ satisfy the symmetry condition $$ f_{i_1 ... i_k}(X_{i_1},...,X_{i_k}) = f_{i_{π(1)} ... i_{π(k)}}(X_{i_{π(1)}},...,X_{i_{π(k)}}) $$ for all permutations $π$ of $\{1,...,k\}$. Note that the expression $i_1 \ne ... \ne i_k$ means that $i_r \ne i_s$ for $r\ne s$. Also, $C_k$ is a constant that depends only on $k$.
△ Less
Submitted 6 December, 1999; v1 submitted 13 September, 1993;
originally announced September 1993.
-
Bounds on the tail probability of U-statistics and quadratic forms
Authors:
Victor H. de la Peña,
Stephen J. Montgomery-Smith
Abstract:
The authors announce a general tail estimate, called a decoupling inequality, for a symmetrized sum of non-linear $k$-correlations of $n>k$ independent random variables.
The authors announce a general tail estimate, called a decoupling inequality, for a symmetrized sum of non-linear $k$-correlations of $n>k$ independent random variables.
△ Less
Submitted 12 September, 1993;
originally announced September 1993.
