-
Colouring a graph with position sets
Authors:
Ullas Chandran S. V.,
Gabriele Di Stefano,
Haritha S.,
Elias John Thomas,
James Tuite
Abstract:
In this paper we consider a colouring version of the general position problem. The \emph{$\gp $-chromatic number} is the smallest number of colours needed to colour $V(G)$ such that each colour class has the no-three-in-line property. We determine bounds on this colouring number in terms of the diameter, general position number, size, chromatic number, cochromatic number and total domination numbe…
▽ More
In this paper we consider a colouring version of the general position problem. The \emph{$\gp $-chromatic number} is the smallest number of colours needed to colour $V(G)$ such that each colour class has the no-three-in-line property. We determine bounds on this colouring number in terms of the diameter, general position number, size, chromatic number, cochromatic number and total domination number and prove realisation results. We also determine it for several graph classes, including Kneser graphs $K(n,2)$, line graphs of complete graphs, complete multipartite graphs, block graphs and Cartesian products. We also show that the $\gp $-colouring problem is NP-complete.
△ Less
Submitted 24 August, 2024;
originally announced August 2024.
-
On the approximability of graph visibility problems
Authors:
Davide Bilò,
Alessia Di Fonso,
Gabriele Di Stefano,
Stefano Leucci
Abstract:
Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph $G$ of $n$ vertices asks to find the largest set of vertices $X\subseteq V(G)$, also called $μ$-set, such that for any two vertices $u,v\in X$, there is a shortest $u,v$-path…
▽ More
Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph $G$ of $n$ vertices asks to find the largest set of vertices $X\subseteq V(G)$, also called $μ$-set, such that for any two vertices $u,v\in X$, there is a shortest $u,v$-path $P$ where all internal vertices of $P$ are not in $X$. This means that $u$ and $v$ are visible w.r.t. $X$. Variations of this problem are known as total, outer, and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside $X$. The mutual-visibility problem and all its variations are known to be $\mathsf{NP}$-complete on graphs of diameter $4$.
In this paper, we design a polynomial-time algorithm that finds a $μ$-set with size $Ω\left( \sqrt{n/ \overline{D}} \right)$, where $\overline D$ is the average distance between any two vertices of $G$. Moreover, we show inapproximability results for all visibility problems on graphs of diameter $2$ and strengthen the inapproximability ratios for graphs of diameter $3$ or larger. More precisely, for graphs of diameter at least $3$ and for every constant $\varepsilon > 0$, we show that mutual-visibility and dual mutual-visibility problems are not approximable within a factor of $n^{1/3-\varepsilon}$, while outer and total mutual-visibility problems are not approximable within a factor of $n^{1/2 - \varepsilon}$, unless $\mathsf{P}=\mathsf{NP}$.
Furthermore we study the relationship between the mutual-visibility number and the general position number in which no three distinct vertices $u,v,w$ of $X$ belong to any shortest path of $G$.
△ Less
Submitted 29 June, 2024;
originally announced July 2024.
-
An optimal algorithm for geodesic mutual visibility on hexagonal grids
Authors:
Sahar Badri,
Serafino Cicerone,
Alessia Di Fonso,
Gabriele Di Stefano
Abstract:
For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through shortest paths). These properties can be obtained if the \textsc{Geodesic Mutual Visibility} (GMV, for short) problem is solved: oblivious robots move along the…
▽ More
For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through shortest paths). These properties can be obtained if the \textsc{Geodesic Mutual Visibility} (GMV, for short) problem is solved: oblivious robots move along the edges of the graph, without collisions, to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means there is a shortest path (i.e., a ``geodesic'') between each pair of robots along which no other robots reside. In this work, we optimally solve GMV on finite hexagonal grids $G_k$. This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in $G_k$.
△ Less
Submitted 29 May, 2024; v1 submitted 22 May, 2024;
originally announced May 2024.
-
Mutual-visibility problems on graphs of diameter two
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Sandi Klavžar,
Ismael G. Yero
Abstract:
The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$-path $P$ so that all internal vertices of $P$ are not in $S$. This is also said as $x,y$ are visible with respect to $S$, or $S$-visible for short. Variations of this problem are known, based on the extension of the v…
▽ More
The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$-path $P$ so that all internal vertices of $P$ are not in $S$. This is also said as $x,y$ are visible with respect to $S$, or $S$-visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside $S$. Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters.
The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankievicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Turán problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.
△ Less
Submitted 4 January, 2024;
originally announced January 2024.
-
Mutual visibility in hypercube-like graphs
Authors:
Serafino Cicerone,
Alessia Di Fonso,
Gabriele Di Stefano,
Alfredo Navarra,
Francesco Piselli
Abstract:
Let $G$ be a graph and $X\subseteq V(G)$. Then, vertices $x$ and $y$ of $G$ are $X$-visible if there exists a shortest $u,v$-path where no internal vertices belong to $X$. The set $X$ is a mutual-visibility set of $G$ if every two vertices of $X$ are $X$-visible, while $X$ is a total mutual-visibility set if any two vertices from $V(G)$ are $X$-visible. The cardinality of a largest mutual-visibili…
▽ More
Let $G$ be a graph and $X\subseteq V(G)$. Then, vertices $x$ and $y$ of $G$ are $X$-visible if there exists a shortest $u,v$-path where no internal vertices belong to $X$. The set $X$ is a mutual-visibility set of $G$ if every two vertices of $X$ are $X$-visible, while $X$ is a total mutual-visibility set if any two vertices from $V(G)$ are $X$-visible. The cardinality of a largest mutual-visibility set (resp. total mutual-visibility set) is the mutual-visibility number (resp. total mutual-visibility number) $μ(G)$ (resp. $μ_t(G)$) of $G$. It is known that computing $μ(G)$ is an NP-complete problem, as well as $μ_t(G)$. In this paper, we study the (total) mutual-visibility in hypercube-like networks (namely, hypercubes, cube-connected cycles, and butterflies). Concerning computing $μ(G)$, we provide approximation algorithms for both hypercubes and cube-connected cycles, while we give an exact formula for butterflies. Concerning computing $μ_t(G)$ (in the literature, already studied in hypercubes), we provide exact formulae for both cube-connected cycles and butterflies.
△ Less
Submitted 28 August, 2023;
originally announced August 2023.
-
Time-optimal geodesic mutual visibility of robots on grids within minimum area
Authors:
Serafino Cicerone,
Alessia Di Fonso,
Gabriele Di Stefano,
Alfredo Navarra
Abstract:
The \textsc{Mutual Visibility} is a well-known problem in the context of mobile robots. For a set of $n$ robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the \textsc{Geodesic Mutual Visibility} ($\GMV$) problem. Robots move along the edges of th…
▽ More
The \textsc{Mutual Visibility} is a well-known problem in the context of mobile robots. For a set of $n$ robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the \textsc{Geodesic Mutual Visibility} ($\GMV$) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a "geodesic") between each pair of robots along which no other robots reside. We study this problem in the context of finite and infinite square grids, for robots operating under the standard Look-Compute-Move model. In both scenarios, we provide resolution algorithms along with formal correctness proofs, highlighting the most relevant peculiarities arising within the different contexts, while optimizing the time complexity.
△ Less
Submitted 3 August, 2023;
originally announced August 2023.
-
Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
Authors:
Serafino Cicerone,
Gabriele Di Stefano
Abstract:
The concept of mutual-visibility in graphs has been recently introduced. If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u, v\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest…
▽ More
The concept of mutual-visibility in graphs has been recently introduced. If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u, v\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class.
△ Less
Submitted 20 July, 2023;
originally announced July 2023.
-
Lower General Position Sets in Graphs
Authors:
Gabriele Di Stefano,
Sandi Klavžar,
Aditi Krishnakumar,
James Tuite,
Ismael Yero
Abstract:
A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower general position number} $\gp ^-(G)$ of $G$, which is the number of vertices in a smallest maximal general position set of $G$. We show that…
▽ More
A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower general position number} $\gp ^-(G)$ of $G$, which is the number of vertices in a smallest maximal general position set of $G$. We show that ${\rm gp}^-(G) = 2$ if and only if $G$ contains a universal line and determine this number for several classes of graphs, including Kneser graphs $K(n,2)$, line graphs of complete graphs, and Cartesian and direct products of two complete graphs. We also prove several realisation results involving the lower general position number, the general position number and the geodetic number, and compare it with the lower version of the monophonic position number. We provide a sharp upper bound on the size of graphs with given lower general position number. Finally we demonstrate that the decision version of the lower general position problem is NP-complete.
△ Less
Submitted 5 January, 2024; v1 submitted 16 June, 2023;
originally announced June 2023.
-
Variety of mutual-visibility problems in graphs
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Lara Drozek,
Jaka Hedzet,
Sandi Klavzar,
Ismael G. Yero
Abstract:
If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$ and has been already investigated. In this pap…
▽ More
If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$ and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be $X$-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.
△ Less
Submitted 29 July, 2023; v1 submitted 3 April, 2023;
originally announced April 2023.
-
Mutual-visibility in strong products of graphs via total mutual-visibility
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Sandi Klavžar,
Ismael G. Yero
Abstract:
Let $G$ be a graph and $X\subseteq V(G)$. Then $X$ is a mutual-visibility set if each pair of vertices from $X$ is connected by a geodesic with no internal vertex in $X$. The mutual-visibility number $μ(G)$ of $G$ is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility s…
▽ More
Let $G$ be a graph and $X\subseteq V(G)$. Then $X$ is a mutual-visibility set if each pair of vertices from $X$ is connected by a geodesic with no internal vertex in $X$. The mutual-visibility number $μ(G)$ of $G$ is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.
△ Less
Submitted 18 April, 2024; v1 submitted 14 October, 2022;
originally announced October 2022.
-
MARIO: Modular and Extensible Architecture for Computing Visual Statistics in RoboCup SPL
Authors:
Domenico D. Bloisi,
Andrea Pennisi,
Cristian Zampino,
Flavio Biancospino,
Francesco Laus,
Gianluca Di Stefano,
Michele Brienza,
Rocchina Romano
Abstract:
This technical report describes a modular and extensible architecture for computing visual statistics in RoboCup SPL (MARIO), presented during the SPL Open Research Challenge at RoboCup 2022, held in Bangkok (Thailand). MARIO is an open-source, ready-to-use software application whose final goal is to contribute to the growth of the RoboCup SPL community. MARIO comes with a GUI that integrates mult…
▽ More
This technical report describes a modular and extensible architecture for computing visual statistics in RoboCup SPL (MARIO), presented during the SPL Open Research Challenge at RoboCup 2022, held in Bangkok (Thailand). MARIO is an open-source, ready-to-use software application whose final goal is to contribute to the growth of the RoboCup SPL community. MARIO comes with a GUI that integrates multiple machine learning and computer vision based functions, including automatic camera calibration, background subtraction, homography computation, player + ball tracking and localization, NAO robot pose estimation and fall detection. MARIO has been ranked no. 1 in the Open Research Challenge.
△ Less
Submitted 20 September, 2022;
originally announced September 2022.
-
GINGER
Authors:
Carlo Altucci,
Francesco Bajardi Emilio Barchiesi,
Andrea Basti,
Nicolò Beverini,
Thomas Braun,
Giorgio Carelli,
Salvatore Capozziello,
Donatella Ciampini,
Fabrizio Davì,
Gaetano De Luca,
Roberto Devoti,
Rita Di Giovambattista,
Giuseppe Di Somma,
Giuseppe Di Stefano,
Angela D. V. Di Virgilio,
Daniela Famiani,
Alberto Frepoli,
Francesco Fuso,
Ivan Giorgio,
Aladino Govoni,
Gaetano Lambiase,
Enrico Maccioni,
Paolo Marsili,
Alessia Mercuri,
Fabio Morsani
, et al. (7 additional authors not shown)
Abstract:
In this paper, we outline the scientific objectives, the experimental layout, and the collaborations envisaged for the GINGER (Gyroscopes IN GEneral Relativity) project. The GINGER project brings together different scientific disciplines aiming at building an array of Ring Laser Gyroscopes (RLGs), exploiting the Sagnac effect, to measure continuously, with sensitivity better than picorad/ s, large…
▽ More
In this paper, we outline the scientific objectives, the experimental layout, and the collaborations envisaged for the GINGER (Gyroscopes IN GEneral Relativity) project. The GINGER project brings together different scientific disciplines aiming at building an array of Ring Laser Gyroscopes (RLGs), exploiting the Sagnac effect, to measure continuously, with sensitivity better than picorad/ s, large bandwidth (ca. 1 kHz), and high dynamic range, the absolute angular rotation rate of the Earth. In the paper, we address the feasibility of the apparatus with respect to the ambitious specifications above, as well as prove how such an apparatus, which will be able to detect strong Earthquakes, very weak geodetic signals, as well as general relativity effects like Lense-Thirring and De Sitter, will help scientific advancements in Theoretical Physics, Geophysics, and Geodesy, among other scientific fields.
△ Less
Submitted 19 September, 2022;
originally announced September 2022.
-
On the Vertex Position Number of Graphs
Authors:
Maya Thankachy,
Elias John Thomas,
Ullas Chandran,
James Tuite,
Gabriele Di Stefano,
Grahame Erskine
Abstract:
In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex $x$ of a connected graph $G$, we say that a set $S \subseteq V(G)$ is an \emph{$x$-position set} if for any $y \in S$ the shortest $x,y$-paths in $G$ contain no point of $S\setminus \{ y\}$. We investigate the largest and smallest orders of maximum $x$-position sets…
▽ More
In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex $x$ of a connected graph $G$, we say that a set $S \subseteq V(G)$ is an \emph{$x$-position set} if for any $y \in S$ the shortest $x,y$-paths in $G$ contain no point of $S\setminus \{ y\}$. We investigate the largest and smallest orders of maximum $x$-position sets in graphs, determining these numbers for common classes of graphs and giving bounds in terms of the girth, vertex degrees, diameter and radius. Finally we discuss the complexity of finding maximum vertex position sets in graphs.
△ Less
Submitted 19 September, 2022; v1 submitted 1 September, 2022;
originally announced September 2022.
-
About the Infinite Windy Firebreak Location problem
Authors:
Marc Demange,
Alessia Di Fonso,
Gabriele Di Stefano,
Pierpaolo Vittorini
Abstract:
The severity of wildfires can be mitigated adopting preventive measures like the construction of firebreaks that are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location. A land of unknown extension is modeled as an infinite undirected graph…
▽ More
The severity of wildfires can be mitigated adopting preventive measures like the construction of firebreaks that are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location. A land of unknown extension is modeled as an infinite undirected graph in which the vertices correspond to areas subject to fire and edges represent the propagation of fire from an area to another. The construction of a firebreak on the territory is modeled as the removal of edges in both directions between two vertices. The number of firebreaks that can be installed depends on budget constraints. We assume that fire ignites in a subset of vertices and propagates to the neighbours. The goal is to select a subset of edges to remove in order to contain the fire and avoid burning an infinite part of the graph. We prove that Infinite Windy Firebreak Location is coNP-complete in restricted cases and we address some polynomial cases. We show that Infinite Windy Firebreak Location polynomially reduces to Min Cut for certain classes of graphs like infinite grid graphs and polyomino-grids.
△ Less
Submitted 11 April, 2022;
originally announced April 2022.
-
On the General Position Number of Mycielskian Graphs
Authors:
Elias John Thomas,
Ullas Chandran,
James Tuite,
Gabriele Di Stefano
Abstract:
The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. The \emph{general position number} of $G$ is the number of vertices in a largest general position set. In this paper we investigate the general position n…
▽ More
The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. The \emph{general position number} of $G$ is the number of vertices in a largest general position set. In this paper we investigate the general position numbers of the Mycielskian of graphs. We give tight upper and lower bounds on the general position number of the Mycielskian of a graph $G$ and investigate the structure of the graphs meeting these bounds. We determine this number exactly for common classes of graphs, including cubic graphs and a wide range of trees.
△ Less
Submitted 30 March, 2024; v1 submitted 15 March, 2022;
originally announced March 2022.
-
On the mutual visibility in Cartesian products and triangle-free graphs
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Sandi Klavzar
Abstract:
Given a graph $G=(V(G), E(G))$ and a set $P\subseteq V(G)$, the following concepts have been recently introduced: $(i)$ two elements of $P$ are \emph{mutually visible} if there is a shortest path between them without further elements of $P$; $(ii)$ $P$ is a \emph{mutual-visibility set} if its elements are pairwise mutually visible; $(iii)$ the \emph{mutual-visibility number} of $G$ is the size of…
▽ More
Given a graph $G=(V(G), E(G))$ and a set $P\subseteq V(G)$, the following concepts have been recently introduced: $(i)$ two elements of $P$ are \emph{mutually visible} if there is a shortest path between them without further elements of $P$; $(ii)$ $P$ is a \emph{mutual-visibility set} if its elements are pairwise mutually visible; $(iii)$ the \emph{mutual-visibility number} of $G$ is the size of any largest mutual-visibility set. %
In this work we continue to investigate about these concepts. We first focus on mutual-visibility in Cartesian products. For this purpose, too, we introduce and investigate independent mutual-visibility sets. In the very special case of the Cartesian product of two complete graphs the problem is shown to be equivalent to the well-known Zarenkiewicz's problem. We also characterize the triangle-free graphs with the mutual-visibility number equal to $3$.
△ Less
Submitted 18 May, 2022; v1 submitted 24 December, 2021;
originally announced December 2021.
-
Mutual Visibility in Graphs
Authors:
Gabriele Di Stefano
Abstract:
Let $G=(V,E)$ be a graph and $P\subseteq V$ a set of points. Two points are mutually visible if there is a shortest path between them without further points. $P$ is a mutual-visibility set if its points are pairwise mutually visible. The mutual-visibility number of $G$ is the size of any largest mutual-visibility set. In this paper we start the study about this new invariant and the mutual-visibil…
▽ More
Let $G=(V,E)$ be a graph and $P\subseteq V$ a set of points. Two points are mutually visible if there is a shortest path between them without further points. $P$ is a mutual-visibility set if its points are pairwise mutually visible. The mutual-visibility number of $G$ is the size of any largest mutual-visibility set. In this paper we start the study about this new invariant and the mutual-visibility sets in undirected graphs. We introduce the mutual-visibility problem which asks to find a mutual-visibility set with a size larger than a given number. We show that this problem is NP-complete, whereas, to check whether a given set of points is a mutual-visibility set is solvable in polynomial time. Then we study mutual-visibility sets and mutual-visibility numbers on special classes of graphs, such as block graphs, trees, grids, tori, complete bipartite graphs, cographs. We also provide some relations of the mutual-visibility number of a graph with other invariants.
△ Less
Submitted 15 July, 2021; v1 submitted 6 May, 2021;
originally announced May 2021.
-
A graph theoretical approach to the firebreak locating problem
Authors:
Marc Demange,
Alessia Di Fonso,
Gabriele Di Stefano,
Pierpaolo Vittorini
Abstract:
In the last decade, wildfires have become wider and more destructive. The climate change and the growth of urban areas may further increase the probability of incidence of large-scale fires. The risk of fire can be lowered with preventive measures. Among them, firefighting lines are used to stop the fire from spreading beyond them. Due to high costs of installation and maintenance, their placement…
▽ More
In the last decade, wildfires have become wider and more destructive. The climate change and the growth of urban areas may further increase the probability of incidence of large-scale fires. The risk of fire can be lowered with preventive measures. Among them, firefighting lines are used to stop the fire from spreading beyond them. Due to high costs of installation and maintenance, their placement must be carefully planned. In this work, we address the wildfire management problem from a theoretical point of view and define a risk function to model the fire diffusion phenomena. The land is modeled by a mixed graph in which vertices are areas subject to fire with a certain probability while edges model the probability of fire spreading from one area to another. To reduce the risk, we introduce the {\sc Windy Firebreak Location} problem that addresses the optimal positioning of firefighting lines under budget constraints. We study the complexity of the problem and prove its hardness even when the graph is planar, bipartite, with maximum degree four and the propagation probabilities are equal to one. We also show an efficient polynomial time algorithm for particular instances on trees.
△ Less
Submitted 18 March, 2021;
originally announced March 2021.
-
On monophonic position sets in graphs
Authors:
Elias John Thomas,
S. V. Ullas Chandran,
James Tuite,
Gabriele Di Stefano
Abstract:
The general position problem in graph theory asks for the largest set $S$ of vertices of a graph $G$ such that no shortest path of $G$ contains more than two vertices of $S$. In this paper we consider a variant of the general position problem called the \emph{monophonic position problem}, obtained by replacing `shortest path' by `induced path'. We prove some basic properties and bounds for the mon…
▽ More
The general position problem in graph theory asks for the largest set $S$ of vertices of a graph $G$ such that no shortest path of $G$ contains more than two vertices of $S$. In this paper we consider a variant of the general position problem called the \emph{monophonic position problem}, obtained by replacing `shortest path' by `induced path'. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem.
△ Less
Submitted 14 December, 2022; v1 submitted 18 December, 2020;
originally announced December 2020.
-
Arbitrary Pattern Formation on Infinite Regular Tessellation Graphs
Authors:
Serafino Cicerone,
Alessia Di Fonso,
Gabriele Di Stefano,
Alfredo Navarra
Abstract:
Given a set R of robots, each one located at different vertices of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that |R|=|F|, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translat…
▽ More
Given a set R of robots, each one located at different vertices of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that |R|=|F|, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical Look-Compute-Move model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph.
△ Less
Submitted 27 October, 2020;
originally announced October 2020.
-
A methodology to design distributed algorithms for mobile entities: the pattern formation problem as case study
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Alfredo Navarra
Abstract:
Following the wide investigation in distributed computing issues by mobile entities of the last two decades, we consider the need of a structured methodology to tackle the arisen problems. The aim is to simplify both the design of the resolution algorithms and the writing of the required correctness proofs. We would encourage the usage of a common framework in order to help both algorithm designer…
▽ More
Following the wide investigation in distributed computing issues by mobile entities of the last two decades, we consider the need of a structured methodology to tackle the arisen problems. The aim is to simplify both the design of the resolution algorithms and the writing of the required correctness proofs. We would encourage the usage of a common framework in order to help both algorithm designer and reviewers in the intricate work of analyzing the proposed resolution strategies. In order to better understand the potentials of our methodology, we consider the Pattern Formation (PF) problem approached in [Fujinaga et al. SIAM J. Comput., 2015] as case study. Since the proposed resolution algorithm has turned out to be inaccurate and also of difficult fixing, we design a new algorithm guided by the proposed methodology, hence fully characterizing the problem.
△ Less
Submitted 26 October, 2020; v1 submitted 23 October, 2020;
originally announced October 2020.
-
Metrics and methods for a systematic comparison of fairness-aware machine learning algorithms
Authors:
Gareth P. Jones,
James M. Hickey,
Pietro G. Di Stefano,
Charanpal Dhanjal,
Laura C. Stoddart,
Vlasios Vasileiou
Abstract:
Understanding and removing bias from the decisions made by machine learning models is essential to avoid discrimination against unprivileged groups. Despite recent progress in algorithmic fairness, there is still no clear answer as to which bias-mitigation approaches are most effective. Evaluation strategies are typically use-case specific, rely on data with unclear bias, and employ a fixed policy…
▽ More
Understanding and removing bias from the decisions made by machine learning models is essential to avoid discrimination against unprivileged groups. Despite recent progress in algorithmic fairness, there is still no clear answer as to which bias-mitigation approaches are most effective. Evaluation strategies are typically use-case specific, rely on data with unclear bias, and employ a fixed policy to convert model outputs to decision outcomes. To address these problems, we performed a systematic comparison of a number of popular fairness algorithms applicable to supervised classification. Our study is the most comprehensive of its kind. It utilizes three real and four synthetic datasets, and two different ways of converting model outputs to decisions. It considers fairness, predictive-performance, calibration quality, and speed of 28 different modelling pipelines, corresponding to both fairness-unaware and fairness-aware algorithms. We found that fairness-unaware algorithms typically fail to produce adequately fair models and that the simplest algorithms are not necessarily the fairest ones. We also found that fairness-aware algorithms can induce fairness without material drops in predictive power. Finally, we found that dataset idiosyncracies (e.g., degree of intrinsic unfairness, nature of correlations) do affect the performance of fairness-aware approaches. Our results allow the practitioner to narrow down the approach(es) they would like to adopt without having to know in advance their fairness requirements.
△ Less
Submitted 8 October, 2020;
originally announced October 2020.
-
Fairness by Explicability and Adversarial SHAP Learning
Authors:
James M. Hickey,
Pietro G. Di Stefano,
Vlasios Vasileiou
Abstract:
The ability to understand and trust the fairness of model predictions, particularly when considering the outcomes of unprivileged groups, is critical to the deployment and adoption of machine learning systems. SHAP values provide a unified framework for interpreting model predictions and feature attribution but do not address the problem of fairness directly. In this work, we propose a new definit…
▽ More
The ability to understand and trust the fairness of model predictions, particularly when considering the outcomes of unprivileged groups, is critical to the deployment and adoption of machine learning systems. SHAP values provide a unified framework for interpreting model predictions and feature attribution but do not address the problem of fairness directly. In this work, we propose a new definition of fairness that emphasises the role of an external auditor and model explicability. To satisfy this definition, we develop a framework for mitigating model bias using regularizations constructed from the SHAP values of an adversarial surrogate model. We focus on the binary classification task with a single unprivileged group and link our fairness explicability constraints to classical statistical fairness metrics. We demonstrate our approaches using gradient and adaptive boosting on: a synthetic dataset, the UCI Adult (Census) dataset and a real-world credit scoring dataset. The models produced were fairer and performant.
△ Less
Submitted 26 June, 2020; v1 submitted 11 March, 2020;
originally announced March 2020.
-
Energy resolution and linearity of XENON1T in the MeV energy range
Authors:
E. Aprile,
J. Aalbers,
F. Agostini,
M. Alfonsi,
L. Althueser,
F. D. Amaro,
V. C. Antochi,
E. Angelino,
J. Angevaare,
F. Arneodo,
D. Barge,
L. Baudis,
B. Bauermeister,
L. Bellagamba,
M. L. Benabderrahmane,
T. Berger,
P. A. Breur,
A. Brown,
E. Brown,
S. Bruenner,
G. Bruno,
R. Budnik,
C. Capelli,
J. M. R. Cardoso,
D. Cichon
, et al. (113 additional authors not shown)
Abstract:
Xenon dual-phase time projection chambers designed to search for Weakly Interacting Massive Particles have so far shown a relative energy resolution which degrades with energy above $\sim$200 keV due to the saturation effects. This has limited their sensitivity in the search for rare events like the neutrinoless double-beta decay of $^{136}$Xe at its $Q$-value, $Q_{ββ}\simeq$ 2.46 MeV. For the XEN…
▽ More
Xenon dual-phase time projection chambers designed to search for Weakly Interacting Massive Particles have so far shown a relative energy resolution which degrades with energy above $\sim$200 keV due to the saturation effects. This has limited their sensitivity in the search for rare events like the neutrinoless double-beta decay of $^{136}$Xe at its $Q$-value, $Q_{ββ}\simeq$ 2.46 MeV. For the XENON1T dual-phase time projection chamber, we demonstrate that the relative energy resolution at 1 $σ/μ$ is as low as (0.80$\pm$0.02) % in its one-ton fiducial mass, and for single-site interactions at $Q_{ββ}$. We also present a new signal correction method to rectify the saturation effects of the signal readout system, resulting in more accurate position reconstruction and indirectly improving the energy resolution. The very good result achieved in XENON1T opens up new windows for the xenon dual-phase dark matter detectors to simultaneously search for other rare events.
△ Less
Submitted 9 September, 2020; v1 submitted 8 March, 2020;
originally announced March 2020.
-
Counterfactual fairness: removing direct effects through regularization
Authors:
Pietro G. Di Stefano,
James M. Hickey,
Vlasios Vasileiou
Abstract:
Building machine learning models that are fair with respect to an unprivileged group is a topical problem. Modern fairness-aware algorithms often ignore causal effects and enforce fairness through modifications applicable to only a subset of machine learning models. In this work, we propose a new definition of fairness that incorporates causality through the Controlled Direct Effect (CDE). We deve…
▽ More
Building machine learning models that are fair with respect to an unprivileged group is a topical problem. Modern fairness-aware algorithms often ignore causal effects and enforce fairness through modifications applicable to only a subset of machine learning models. In this work, we propose a new definition of fairness that incorporates causality through the Controlled Direct Effect (CDE). We develop regularizations to tackle classical fairness measures and present a causal regularization that satisfies our new fairness definition by removing the impact of unprivileged group variables on the model outcomes as measured by the CDE. These regularizations are applicable to any model trained using by iteratively minimizing a loss through differentiation. We demonstrate our approaches using both gradient boosting and logistic regression on: a synthetic dataset, the UCI Adult (Census) Dataset, and a real-world credit-risk dataset. Our results were found to mitigate unfairness from the predictions with small reductions in model performance.
△ Less
Submitted 26 February, 2020; v1 submitted 25 February, 2020;
originally announced February 2020.
-
Winter long duration stratospheric balloons from Polar regions
Authors:
Francesco Piacentini,
Alessandro Coppolecchia,
Paolo de Bernardis,
Giuseppe Di Stefano,
Alessandro Iarocci,
Luca Lamagna,
Silvia Masi,
Steven Peterzen,
Romeo Giovanni
Abstract:
A new opportunity for astronomy, cosmology, physics, and atmospheric observations is the possibility to fly stratospheric payloads at 30 - 40 km of altitude during the polar night. The absence of solar irradiation for long periods, and the extremely low temperature and stable environment of the winter stratosphere represent ideal environmental conditions while performing astrophysical observations…
▽ More
A new opportunity for astronomy, cosmology, physics, and atmospheric observations is the possibility to fly stratospheric payloads at 30 - 40 km of altitude during the polar night. The absence of solar irradiation for long periods, and the extremely low temperature and stable environment of the winter stratosphere represent ideal environmental conditions while performing astrophysical observations. Here we present a small and efficient platform, able to communicate, supply power and navigate in the harsh environment of the polar stratosphere. After a balloon failure in January 2017, the payload was successfully flown in December 2017 from 78$^\circ$N, in Longyearbyen, Svalbard, Norway. Duration was limited to 21 hr, due to a southern trajectory that caused solar illumination and loss of lift. The instrument acquired and transmitted environmental data, and the thermal performance of the power system are outstanding. The payload also included a set of attitude sensors, to monitor payload movements. The information collected on this flight is essential to qualify the attitude control system sensors, and for the design if the thermal and power system of the next generation LSPE-SWIPE telescope, devoted to the measurement of the polarization of the Cosmic Microwave Background radiation from a stratospheric balloon during the Arctic polar night.
△ Less
Submitted 12 October, 2018;
originally announced October 2018.
-
Ultrastrong coupling probed by Coherent Population Transfer
Authors:
G. Falci,
A. Ridolfo,
P. G. Di Stefano,
E. Paladino
Abstract:
Light-matter interaction, and the understanding of the fundamental physics behind, is the scenario of emerging quantum technologies. Solid state devices allow the exploration of new regimes where ultrastrong coupling (USC) strengths are comparable to subsystem energies, and new exotic phenomena like quantum phase transitions and ground-state entanglement occur. While experiments so far provided on…
▽ More
Light-matter interaction, and the understanding of the fundamental physics behind, is the scenario of emerging quantum technologies. Solid state devices allow the exploration of new regimes where ultrastrong coupling (USC) strengths are comparable to subsystem energies, and new exotic phenomena like quantum phase transitions and ground-state entanglement occur. While experiments so far provided only spectroscopic evidence of USC, we propose a new dynamical protocol for detecting virtual photon pairs in the dressed eigenstates. This is the fingerprint of the violated conservation of the number of excitations, which heralds the symmetry broken by USC. We show that in flux-based superconducting architectures this photon production channel can be coherenly amplified by Stimulated Raman Adiabatic Passage (STIRAP). This provides a unique tool for an unambiguous dynamical detection of USC in present day hardware. Implementing this protocol would provide a benchmark for control of the dynamics of USC architectures, in view of applications to quantum information and microwave quantum photonics.
△ Less
Submitted 27 March, 2019; v1 submitted 2 August, 2017;
originally announced August 2017.
-
Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approach
Authors:
Serafino Cicerone,
Gabriele Di Stefano,
Alfredo Navarra
Abstract:
Given any multiset F of points in the Euclidean plane and a set R of robots such that |R|=|F|, the Arbitrary Pattern Formation (APF) problem asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct…
▽ More
Given any multiset F of points in the Euclidean plane and a set R of robots such that |R|=|F|, the Arbitrary Pattern Formation (APF) problem asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct position. When active, a robot operates in standard LCM cycles. Robots are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. So far, the problem has been mainly addressed by assuming chirality, that is robots share a common left-right orientation. We are interested in removing such a restriction. While working on the subject, we faced several issues that required close attention. We deeply investigated how such difficulties were overcome in the literature, revealing that crucial arguments for the correctness proof of the existing algorithms have been neglected. The systematic lack of rigorous arguments with respect to necessary conditions required for providing correctness proofs deeply affects the validity as well as the relevance of strategies proposed in the literature. Here we design a new deterministic distributed algorithm that fully characterizes APF showing its equivalence with the well-known Leader Election problem in the asynchronous model without chirality. Our approach is characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness. In addition to the relevance of our achievements, our techniques might help in revising previous results. In fact, it comes out that well-established results like [Fujinaga et al, SIAM J. Comp. 44(3) 2015], more recent approaches like [Bramas et al, PODC and SSS 2016] and 'unofficial' results like [Dieudonne et al, arXiv:0902.2851] revealed to be not correct.
△ Less
Submitted 6 February, 2018; v1 submitted 8 June, 2017;
originally announced June 2017.
-
Advances in quantum control of three-level superconducting circuit architectures
Authors:
G. Falci,
P. G. Di Stefano,
A. Ridolfo,
A. D'Arrigo,
G. S. Paraoanu,
E. Paladino
Abstract:
Advanced control in Lambda ($Λ$) scheme of a solid state architecture of artificial atoms and quantized modes would allow the translation to the solid-state realm of a whole class of phenomena from quantum optics, thus exploiting new physics emerging in larger integrated quantum networks and for stronger couplings. However control solid-state devices has constraints coming from selection rules, du…
▽ More
Advanced control in Lambda ($Λ$) scheme of a solid state architecture of artificial atoms and quantized modes would allow the translation to the solid-state realm of a whole class of phenomena from quantum optics, thus exploiting new physics emerging in larger integrated quantum networks and for stronger couplings. However control solid-state devices has constraints coming from selection rules, due to symmetries which on the other hand yield protection from decoherence, and from design issues, for instance that coupling to microwave cavities is not directly switchable. We present two new schemes for the $Λ$-STIRAP control problem with the constraint of one or two classical driving fields being always-on. We show how these protocols are converted to apply to circuit-QED architectures. We finally illustrate an application to coherent spectroscopy of the so called ultrastrong atom-cavity coupling regime.
△ Less
Submitted 3 April, 2017;
originally announced April 2017.
-
Non-equilibrium thermodynamics of continuously measured quantum systems: a circuit-QED implementation
Authors:
P. G. Di Stefano,
J. J. Alonso,
E. Lutz,
G. Falci,
M. Paternostro
Abstract:
We propose a fully operational framework to study the non-equilibrium thermodynamics of a quantum system $S$ that is coupled to a detector $D$ whose state is continuously monitored, allowing to single out individual quantum trajectories of $S$. We focus on detailed fluctuation theorems and characterize the entropy production of the system. We establish fundamental differences with respect to the t…
▽ More
We propose a fully operational framework to study the non-equilibrium thermodynamics of a quantum system $S$ that is coupled to a detector $D$ whose state is continuously monitored, allowing to single out individual quantum trajectories of $S$. We focus on detailed fluctuation theorems and characterize the entropy production of the system. We establish fundamental differences with respect to the thermodynamic of unmonitored, unitarily evolved systems. We consider the paradigmatic example of circuit-QED, where superconducting qubits can be coupled to a continuously monitored resonator and show numerical simulations using state of the art experimental parameters.
△ Less
Submitted 26 October, 2018; v1 submitted 3 April, 2017;
originally announced April 2017.
-
Coherent manipulation of noise-protected superconducting artificial atoms in the Lambda scheme
Authors:
P. G. Di Stefano,
E. Paladino,
T. J. Pope,
G. Falci
Abstract:
We propose a new protocol for thr manipulation of a three-level artificial atom in Lambda ($Λ$) configuration in the absence of a direct pump coupling. It allows faithful, selective and robust population transfer analogous to stimulated Raman adiabatic passage ($Λ$-STIRAP), in highly noise protected superconducting artificial atoms. It combines the use of a two-photon pump pulse with suitable adva…
▽ More
We propose a new protocol for thr manipulation of a three-level artificial atom in Lambda ($Λ$) configuration in the absence of a direct pump coupling. It allows faithful, selective and robust population transfer analogous to stimulated Raman adiabatic passage ($Λ$-STIRAP), in highly noise protected superconducting artificial atoms. It combines the use of a two-photon pump pulse with suitable advanced control, operated by a slow modulation of the phase of the external fields, leveraging on the stability of semiclassical microwave drives. This protocol is a building block for novel tasks in complex quantum architectures. Its demonstration would be a benchmark for the implementation of a class of multilevel advanced control procedures for quantum computation and microwave quantum photonics in systems based on artificial atoms.
△ Less
Submitted 28 May, 2016; v1 submitted 18 September, 2015;
originally announced September 2015.
-
Population transfer in a Lambda system induced by detunings
Authors:
P. G. Di Stefano,
E. Paladino,
A. D'Arrigo,
G. Falci
Abstract:
In this paper we propose a new protocol to achieve coherent population transfer between two states in a three-level atom by using two ac fields. It is based on the physics of Stimulated Raman Adiabatic Passage (STIRAP), but it is implemented with the constraint of a reduced control, namely one of the fields cannot be switched off. A combination of frequency chirps is used with resonant fields, all…
▽ More
In this paper we propose a new protocol to achieve coherent population transfer between two states in a three-level atom by using two ac fields. It is based on the physics of Stimulated Raman Adiabatic Passage (STIRAP), but it is implemented with the constraint of a reduced control, namely one of the fields cannot be switched off. A combination of frequency chirps is used with resonant fields, allowing to achieve approximate destructive interference, despite of the fact that an exact dark state does not exist. This new chirped STIRAP protocol is tailored for applications to artificial atoms, where architectures with several elementary units can be strongly coupled but where the possibility of switching on and off such couplings is often very limited. Demonstration of this protocol would be a benchmark for the implementation of a class of multilevel advanced control procedures for quantum computation and microwave quantum photonics in artificial atoms.
△ Less
Submitted 13 May, 2015;
originally announced May 2015.
-
Design of a Lambda configuration in artificial coherent nanostructures
Authors:
P. G. Di Stefano,
E. Paladino,
A. D'Arrigo,
B. Spagnolo,
G. Falci
Abstract:
The implementation of a three-level Lambda System in artificial atoms would allow to perform advanced control tasks typical of quantum optics in the solid state realm, with photons in the $\mathrm{μm}$/mm range. However hardware constraints put an obstacle since protection from decoherence is often conflicting with efficient coupling to external fields. We address the problem of performing convent…
▽ More
The implementation of a three-level Lambda System in artificial atoms would allow to perform advanced control tasks typical of quantum optics in the solid state realm, with photons in the $\mathrm{μm}$/mm range. However hardware constraints put an obstacle since protection from decoherence is often conflicting with efficient coupling to external fields. We address the problem of performing conventional STImulated Raman Adiabatic Passage (STIRAP) in the presence of low-frequency noise. We propose two strategies to defeat decoherence, based on "optimal symmetry breaking" and dynamical decoupling. We suggest how to apply to the different implementations of superconducting artificial atoms, stressing the key role of non-Markovianity.
△ Less
Submitted 20 February, 2015;
originally announced February 2015.
-
Properties of Galactic cirrus clouds observed by BOOMERanG
Authors:
M. Veneziani,
P. A. R. Ade,
J. J. Bock,
A. Boscaleri,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. De Troia,
G. Di Stefano,
K. M. Ganga,
W. C. Jones,
T. S. Kisner,
A. E. Lange,
C. J. MacTavish,
S. Masi,
P. D. Mauskopf,
T. E. Montroy,
P. Natoli,
C. B. Netterfield,
E. Pascale,
F. Piacentini,
D. Pietrobon,
G. Polenta,
S. Ricciardi
, et al. (2 additional authors not shown)
Abstract:
The physical properties of galactic cirrus emission are not well characterized. BOOMERanG is a balloon-borne experiment designed to study the cosmic microwave background at high angular resolution in the millimeter range. The BOOMERanG 245 and 345GHz channels are sensitive to interstellar signals, in a spectral range intermediate between FIR and microwave frequencies. We look for physical charac…
▽ More
The physical properties of galactic cirrus emission are not well characterized. BOOMERanG is a balloon-borne experiment designed to study the cosmic microwave background at high angular resolution in the millimeter range. The BOOMERanG 245 and 345GHz channels are sensitive to interstellar signals, in a spectral range intermediate between FIR and microwave frequencies. We look for physical characteristics of cirrus structures in a region at high galactic latitudes (b~-40°) where BOOMERanG performed its deepest integration, combining the BOOMERanG data with other available datasets at different wavelengths. We have detected eight emission patches in the 345 GHz map, consistent with cirrus dust in the Infrared Astronomical Satellite maps. The analysis technique we have developed allows to identify the location and the shape of cirrus clouds, and to extract the flux from observations with different instruments at different wavelengths and angular resolutions. We study the integrated flux emitted from these cirrus clouds using data from Infrared Astronomical Satellite (IRAS), DIRBE, BOOMERanG and Wilkinson Microwave Anisotropy Probe (WMAP) in the frequency range 23-3000 GHz (13 mm 100 micron wavelength). We fit the measured spectral energy distributions with a combination of a grey body and a power-law spectra considering two models for the thermal emission. The temperature of the thermal dust component varies in the 7 - 20 K range and its emissivity spectral index is in the 1 - 5 range. We identified a physical relation between temperature and spectral index as had been proposed in previous works. This technique can be proficiently used for the forthcoming Planck and Herschel missions data.
△ Less
Submitted 20 April, 2010; v1 submitted 28 July, 2009;
originally announced July 2009.
-
BOOMERanG Constraints on Primordial Non-Gaussianity from Analytical Minkowski Functionals
Authors:
P. Natoli,
G. De Troia,
C. Hikage,
E. Komatsu,
M. Migliaccio,
P. A. R. Ade,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. de Gasperis,
A. de Oliveira-Costa,
G. Di Stefano,
E. Hivon,
T. S. Kisner,
W. C. Jones,
A. E. Lange,
S. Masi,
P. D. Mauskopf,
C. J. MacTavish,
A. Melchiorri,
T. E. Montroy
, et al. (10 additional authors not shown)
Abstract:
We use Minkowski Functionals (MF) to constrain a primordial non-Gaussian contribution to the CMB intensity field as observed in the 150 GHz and 145 GHz BOOMERanG maps from the 1998 and 2003 flights, respectively, performing for the first time a joint analysis of the two datasets. A perturbative expansion of the MF formulae in the limit of a weakly non-Gaussian field yields analytical formulae, d…
▽ More
We use Minkowski Functionals (MF) to constrain a primordial non-Gaussian contribution to the CMB intensity field as observed in the 150 GHz and 145 GHz BOOMERanG maps from the 1998 and 2003 flights, respectively, performing for the first time a joint analysis of the two datasets. A perturbative expansion of the MF formulae in the limit of a weakly non-Gaussian field yields analytical formulae, derived by Hikage et al. (2006), which can be used to constrain the coupling parameter f_NL without the need for non-Gaussian simulations. We find -1020<f_NL<390 at 95% CL, significantly improving the previous constraints by De Troia et al. (2007) on the BOOMERanG 2003 dataset. These are the best f_NL limits to date for suborbital probes.
△ Less
Submitted 27 May, 2009;
originally announced May 2009.
-
Subdegree Sunyaev-Zel'dovich Signal from Multifrequency BOOMERanG observations
Authors:
M. Veneziani,
A. Amblard,
A. Cooray,
F. Piacentini,
D. Pietrobon,
P. Serra,
P. A. R. Ade,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
P. Cabella,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. De Troia,
G. Di Stefano,
K. M. Ganga,
E. Hivon,
W. C. Jones,
T. S. Kisner,
A. E. Lange,
C. J. MacTavish
, et al. (14 additional authors not shown)
Abstract:
The Sunyaev-Zel'dovich (SZ) effect is the inverse Compton-scattering of cosmic microwave background (CMB) photons by hot electrons in the intervening gas throughout the universe. The effect has a distinct spectral signature that allows its separation from other signals in multifrequency CMB datasets. Using CMB anisotropies measured at three frequencies by the BOOMERanG 2003 flight we constrain S…
▽ More
The Sunyaev-Zel'dovich (SZ) effect is the inverse Compton-scattering of cosmic microwave background (CMB) photons by hot electrons in the intervening gas throughout the universe. The effect has a distinct spectral signature that allows its separation from other signals in multifrequency CMB datasets. Using CMB anisotropies measured at three frequencies by the BOOMERanG 2003 flight we constrain SZ fluctuations in the 10 arcmin to 1 deg angular range. Propagating errors and potential systematic effects through simulations, we obtain an overall upper limit of 15.3 uK (2 sigma) for rms SZ fluctuations in a broad bin between multipoles of of 250 and 1200 at the Rayleigh-Jeans (RJ) end of the spectrum. When combined with other CMB anisotropy and SZ measurements, we find that the local universe normalization of the density perturbations is sigma-8(SZ) < 0.96 at the 95% confidence level, consistent with sigma-8 determined from primordial perturbations.
△ Less
Submitted 26 August, 2009; v1 submitted 28 April, 2009;
originally announced April 2009.
-
Searching for non Gaussian signals in the BOOMERanG 2003 CMB maps
Authors:
G. De Troia,
P. A. R. Ade,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
P. Cabella,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. Di Stefano,
P. G. Ferreira,
E. Hivon,
A. H. Jaffe,
T. S. Kisner,
M. Kunz,
W. C. Jones,
A. E. Lange,
M. Liguori,
S. Masi,
S. Matarrese,
P. D. Mauskopf,
C. J. MacTavish
, et al. (16 additional authors not shown)
Abstract:
We analyze the BOOMERanG 2003 (B03) 145 GHz temperature map to constrain the amplitude of a non Gaussian, primordial contribution to CMB fluctuations. We perform a pixel space analysis restricted to a portion of the map chosen in view of high sensitivity, very low foreground contamination and tight control of systematic effects. We set up an estimator based on the three Minkowski functionals whi…
▽ More
We analyze the BOOMERanG 2003 (B03) 145 GHz temperature map to constrain the amplitude of a non Gaussian, primordial contribution to CMB fluctuations. We perform a pixel space analysis restricted to a portion of the map chosen in view of high sensitivity, very low foreground contamination and tight control of systematic effects. We set up an estimator based on the three Minkowski functionals which relies on high quality simulated data, including non Gaussian CMB maps. We find good agreement with the Gaussian hypothesis and derive the first limits based on BOOMERanG data for the non linear coupling parameter f_NL as -300<f_NL<650 at 68% CL and -800<f_NL<1050 at 95% CL.
△ Less
Submitted 19 October, 2007; v1 submitted 11 May, 2007;
originally announced May 2007.
-
A Measurement of the CMB <EE> Spectrum from the 2003 Flight of BOOMERANG
Authors:
T. E. Montroy,
P. A. R. Ade,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
P. Cabella,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. De Troia,
G. di Stefano,
E. Hivon,
A. H. Jaffe,
T. S. Kisner,
W. C. Jones,
A. E. Lange,
S. Masi,
P. D. Mauskopf,
C. J. MacTavish,
A. Melchiorri,
P. Natoli,
C. B. Netterfield
, et al. (12 additional authors not shown)
Abstract:
We report measurements of the CMB polarization power spectra from the January 2003 Antarctic flight of BOOMERANG. The primary results come from six days of observation of a patch covering 0.22% of the sky centered near R.A. = 82.5 deg., Dec= -45 deg. The observations were made using four pairs of polarization sensitive bolometers operating in bands centered at 145 GHz. Using two independent anal…
▽ More
We report measurements of the CMB polarization power spectra from the January 2003 Antarctic flight of BOOMERANG. The primary results come from six days of observation of a patch covering 0.22% of the sky centered near R.A. = 82.5 deg., Dec= -45 deg. The observations were made using four pairs of polarization sensitive bolometers operating in bands centered at 145 GHz. Using two independent analysis pipelines, we measure a non-zero <EE> signal in the range 100< l <1000 with a significance 4.8-sigma, a 2-sigma upper limit of 8.6 uK^2 for any <BB> contribution, and a 2-sigma upper limit of 7.0 uK^2 for the <EB> spectrum. Estimates of foreground intensity fluctuations and the non-detection of <BB> and <EB> signals rule out any significant contribution from galactic foregrounds. The results are consistent with a Lambda-CDM cosmology seeded by adiabatic perturbations. We note that this is the first detection of CMB polarization with bolometric detectors.
△ Less
Submitted 21 July, 2005;
originally announced July 2005.
-
Instrument, Method, Brightness and Polarization Maps from the 2003 flight of BOOMERanG
Authors:
S Masi,
P Ade,
J Bock,
J Bond,
J Borrill,
A Boscaleri,
P Cabella,
C Contaldi,
B Crill,
P de Bernardis,
G De Gasperis,
A de Oliveira-Costa,
G De Troia,
G Di Stefano,
P Ehlers,
E Hivon,
V Hristov,
A Iacoangeli,
A Jaffe,
W Jones,
T Kisner,
A Lange,
C MacTavish,
C Marini-Bettolo,
P Mason
, et al. (19 additional authors not shown)
Abstract:
We present the BOOMERanG-03 experiment and maps of the Stokes parameters I, Q, U of the microwave sky obtained during a 14 day balloon flight in 2003. Three regions of the southern sky were surveyed: a deep survey (~ 90 square degrees) and a shallow survey (~ 750 square degrees) at high Galactic latitudes (both centered at RA ~ 5.5 h, dec ~ -45 deg) and a survey of ~ 300 square degrees across th…
▽ More
We present the BOOMERanG-03 experiment and maps of the Stokes parameters I, Q, U of the microwave sky obtained during a 14 day balloon flight in 2003. Three regions of the southern sky were surveyed: a deep survey (~ 90 square degrees) and a shallow survey (~ 750 square degrees) at high Galactic latitudes (both centered at RA ~ 5.5 h, dec ~ -45 deg) and a survey of ~ 300 square degrees across the Galactic plane at RA ~ 9.1 h, dec ~ -47 deg. All three surveys were carried out in three wide frequency bands centered at 145, 245 and 345 GHz, with an angular resolution of ~ 10'. The 145 GHz maps of Stokes I are dominated by Cosmic Microwave Background (CMB) temperature anisotropy, which is mapped with high signal to noise ratio. The measured anisotropy pattern is consistent with the pattern measured in the same region by BOOMERanG-98 and by WMAP. The 145 GHz maps of Stokes Q and U provide a robust statistical detection of polarization of the CMB when subjected to a power spectrum analysis. This amplitude of the polarization is consistent with that of the CMB in the $Λ$CDM cosmological scenario. At 145 GHz, in the CMB surveys, the intensity and polarization of the astrophysical foregrounds are found to be negligible with respect to the cosmological signal. At 245 and 345 GHz we detect ISD emission correlated to the 3000 GHz IRAS/DIRBE maps, and give upper limits for any other non-CMB component. We also present intensity maps of the surveyed section of the Galactic plane. These are compared to monitors of different interstellar components, showing that a variety of emission mechanisms is present in that region.
△ Less
Submitted 21 July, 2005;
originally announced July 2005.
-
A measurement of the polarization-temperature angular cross power spectrum of the Cosmic Microwave Background from the 2003 flight of BOOMERANG
Authors:
F Piacentini,
P Ade,
J Bock,
J Bond,
J Borrill,
A Boscaleri,
P Cabella,
C Contaldi,
B Crill,
P de Bernardis,
G De Gasperis,
A de Oliveira-Costa,
G De Troia,
G Di Stefano,
E Hivon,
A Jaffe,
T Kisner,
W Jones,
A Lange,
S Masi,
P Mauskopf,
C MacTavish,
A Melchiorri,
T Montroy,
P Natoli
, et al. (12 additional authors not shown)
Abstract:
We present a measurement of the temperature-polarization angular cross power spectrum, <TE>, of the Cosmic Microwave Background. The result is based on $\sim 200$ hours of data from 8 polarization sensitive bolometers operating at 145 GHz during the 2003 flight of BOOMERANG. We detect a significant <TE> correlation in the $\ell$-range between 50 and 950 with a statistical significance > 3.5 sigm…
▽ More
We present a measurement of the temperature-polarization angular cross power spectrum, <TE>, of the Cosmic Microwave Background. The result is based on $\sim 200$ hours of data from 8 polarization sensitive bolometers operating at 145 GHz during the 2003 flight of BOOMERANG. We detect a significant <TE> correlation in the $\ell$-range between 50 and 950 with a statistical significance > 3.5 sigma. Contamination by polarized foreground emission and systematic effects are negligible in comparison with statistical uncertainty. The spectrum is consistent with previous detections and with the "concordance model" that assumes adiabatic initial conditions. This is the first measurement of <TE> using bolometric detectors.
△ Less
Submitted 21 July, 2005;
originally announced July 2005.
-
Cosmological Parameters from the 2003 flight of BOOMERANG
Authors:
C. J. MacTavish,
P. A. R. Ade,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
P. Cabella,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. De Troia,
G. Di Stefano,
E. Hivon,
A. H. Jaffe,
W. C. Jones,
T. S. Kisner,
A. E. Lange,
A. M. Lewis,
S. Masi,
P. D. Mauskopf,
A. Melchiorri,
T. E. Montroy,
P. Natoli
, et al. (13 additional authors not shown)
Abstract:
We present the cosmological parameters from the CMB intensity and polarization power spectra of the 2003 Antarctic flight of the BOOMERANG telescope. The BOOMERANG data alone constrains the parameters of the $Λ$CDM model remarkably well and is consistent with constraints from a multi-experiment combined CMB data set. We add LSS data from the 2dF and SDSS redshift surveys to the combined CMB data…
▽ More
We present the cosmological parameters from the CMB intensity and polarization power spectra of the 2003 Antarctic flight of the BOOMERANG telescope. The BOOMERANG data alone constrains the parameters of the $Λ$CDM model remarkably well and is consistent with constraints from a multi-experiment combined CMB data set. We add LSS data from the 2dF and SDSS redshift surveys to the combined CMB data set and test several extensions to the standard model including: running of the spectral index, curvature, tensor modes, the effect of massive neutrinos, and an effective equation of state for dark energy. We also include an analysis of constraints to a model which allows a CDM isocurvature admixture.
△ Less
Submitted 21 July, 2005;
originally announced July 2005.
-
A Measurement of the Angular Power Spectrum of the CMB Temperature Anisotropy from the 2003 Flight of Boomerang
Authors:
W. C. Jones,
P Ade,
J Bock,
J Bond,
J Borrill,
A Boscaleri,
P Cabella,
C Contaldi,
B Crill,
P de Bernardis,
G De Gasperis,
A de Oliveira-Costa,
G De Troia,
G Di Stefano,
E Hivon,
A Jaffe,
T Kisner,
A Lange,
C MacTavish,
S Masi,
P Mauskopf,
A Melchiorri,
T Montroy,
P Natoli,
B Netterfield
, et al. (12 additional authors not shown)
Abstract:
We report on observations of the Cosmic Microwave Background (CMB) obtained during the January 2003 flight of Boomerang . These results are derived from 195 hours of observation with four 145 GHz Polarization Sensitive Bolometer (PSB) pairs, identical in design to the four 143 GHz Planck HFI polarized pixels. The data include 75 hours of observations distributed over 1.84% of the sky with an add…
▽ More
We report on observations of the Cosmic Microwave Background (CMB) obtained during the January 2003 flight of Boomerang . These results are derived from 195 hours of observation with four 145 GHz Polarization Sensitive Bolometer (PSB) pairs, identical in design to the four 143 GHz Planck HFI polarized pixels. The data include 75 hours of observations distributed over 1.84% of the sky with an additional 120 hours concentrated on the central portion of the field, itself representing 0.22% of the full sky. From these data we derive an estimate of the angular power spectrum of temperature fluctuations of the CMB in 24 bands over the multipole range (50 < l < 1500). A series of features, consistent with those expected from acoustic oscillations in the primordial photon-baryon fluid, are clearly evident in the power spectrum, as is the exponential damping of power on scales smaller than the photon mean free path at the epoch of last scattering (l > 900). As a consistency check, the collaboration has performed two fully independent analyses of the time ordered data, which are found to be in excellent agreement.
△ Less
Submitted 21 July, 2005;
originally announced July 2005.
-
Measuring CMB Polarization with BOOMERANG
Authors:
T. Montroy,
P. A. R. Ade,
A. Balbi,
J. J. Bock,
J. R. Bond,
J. Borrill,
A. Boscaleri,
P. Cabella,
C. R. Contaldi,
B. P. Crill,
P. de Bernardis,
G. De Gasperis,
A. de Oliveira-Costa,
G. De Troia,
G. di Stefano,
K. Ganga,
E. Hivon,
V. V. Hristov,
A. Iacoangeli,
A. H. Jaffe,
T. S. Kisner,
W. C. Jones,
A. E. Lange,
S. Masi,
P. D. Mauskopf
, et al. (16 additional authors not shown)
Abstract:
BOOMERANG is a balloon-borne telescope designed for long duration (LDB) flights around Antarctica. The second LDB Flight of BOOMERANG took place in January 2003. The primary goal of this flight was to measure the polarization of the CMB. The receiver uses polarization sensitive bolometers at 145 GHz. Polarizing grids provide polarization sensitivity at 245 and 345 GHz. We describe the BOOMERANG…
▽ More
BOOMERANG is a balloon-borne telescope designed for long duration (LDB) flights around Antarctica. The second LDB Flight of BOOMERANG took place in January 2003. The primary goal of this flight was to measure the polarization of the CMB. The receiver uses polarization sensitive bolometers at 145 GHz. Polarizing grids provide polarization sensitivity at 245 and 345 GHz. We describe the BOOMERANG telescope noting changes made for 2003 LDB flight, and discuss some of the issues involved in the measurement of polarization with bolometers. Lastly, we report on the 2003 flight and provide an estimate of the expected results.
△ Less
Submitted 15 September, 2003; v1 submitted 29 May, 2003;
originally announced May 2003.
