text:
Recoloring graphs via tree decompositionsThe authors are supported by the ANR Grant EGOS (2012-2015) 12 JS02 002 01.

# Recoloring graphs via tree decompositions††thanks: The authors are supported by the ANR Grant EGOS (2012-2015) 12 JS02 002 01.

Marthe Bonamy, Nicolas Bousquet
LIRMM, Université Montpellier 2, CNRS
{marthe.bonamy, nicolas.bousquet}@lirmm.fr
###### Abstract

Let be an integer. Two vertex -colorings of a graph are adjacent if they differ on exactly one vertex. A graph is -mixing if any proper -coloring can be transformed into any other through a sequence of adjacent proper -colorings. Jerrum proved that any graph is -mixing if is at least the maximum degree plus two. We first improve Jerrum’s bound using the grundy number, which is the worst number of colors in a greedy coloring.

Any graph is -mixing, where is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two -colorings is at most quadratic (which is optimal up to a constant factor), a problem left open in Bonamy et al. (2012).

We also prove that given any two -colorings of a cograph (resp. distance-hereditary graph) , we can find a linear (resp. quadratic) sequence between them. In both cases, the bounds cannot be improved by more than a constant factor for a fixed . The graph classes are also optimal in some sense: one of the smallest interesting superclass of distance-hereditary graphs corresponds to comparability graphs, for which no such property holds (even when relaxing the constraint on the length of the sequence). As for cographs, they are equivalently the graphs with no induced , and there exist -free graphs that admit no sequence between two of their -colorings.

All the proofs are constructivist and lead to polynomial-time recoloring algorithms.

Keywords: Reconfiguration problems, vertex coloring, treewidth, distance-hereditary, cograph, grundy number.

## 1 Introduction

Reconfiguration problems (see [13, 16, 17] for instance) consist in finding step-by-step transformations between two feasible solutions such that all intermediate results are also feasible. Such problems model dynamic situations where a given solution is in place and has to be modified, but no property disruption can be afforded. In this paper our reference problem is vertex coloring.

In the whole paper, is a graph where denotes the size of and is an integer. For standard definitions and notations on graphs, we refer the reader to [12]. A (proper) -coloring of is a function such that, for every edge , . The chromatic number of a graph is the smallest such that admits a -coloring.

Two -colorings are adjacent if they differ on exactly one vertex. The -recoloring graph of , denoted and defined for any , is the graph whose vertices are -colorings of , with the adjacency defined above. Note that two colorings equivalent up to color permutation are distinct vertices in the recoloring graph. The graph is -mixing if is connected. Cereceda, van den Heuvel and Johnson characterized the -mixing graphs and provided an algorithm to recognize them [9, 10]. The easiest way to prove that a graph is not -mixing is to exhibit a frozen -coloring of , i.e. a coloring in which all vertices are adjacent to vertices of all other colors. Such a coloring is an isolated vertex in .

Deciding whether a graph is -mixing is -complete for  [7]. The -recoloring diameter of a -mixing graph is the diameter of . In other words, it is the minimum for which any -coloring can be transformed into any other through a sequence of at most adjacent -colorings. The mixing number of is the minimum integer for which is -mixing for every . It can be arbitrarily larger than the minimum for which is -mixing [8] (thus arbitrarily larger than its chromatic number). Indeed, for complete bipartite graphs minus a matching, the chromatic number equals two, any 3-coloring can be transformed into any other through a linear sequence of 3-colorings if there are at least four vertices on each side of the bipartition, and the mixing number is arbitrarily large (see Fig. 1). Throughout the paper, our goal is to determine bounds on the mixing number of graphs and prove that the corresponding recoloring diameter is polynomial. Note that there exists a family of graphs for which there are two colorings that can be transformed one into the other but not through a polynomial sequence [7].

Jerrum [18] proved that , where denotes the maximum degree of . Let be an order on . We denote by the neighborhood of . In the greedy coloring of relative to , every has the smallest color that does not appear in . Introduced in [11], the grundy number is the maximum, over all the orders , of the number of colors used in . So is the worst number of colors in a greedy coloring of . In Section 3, we prove that any graph is -mixing in linear time. The corresponding diameter is at most , and we give a polynomial-time algorithm to find a sequence of length at most .

###### Theorem 1.

For any graph , if , then is -mixing and the -recoloring diameter is at most .

Theorem 1 improves Jerrum’s bound since and can be arbitrarily smaller, on stars for instance.

Besides, the bound is tight on complete bipartite graphs minus a matching [8] (see Figure 1). Indeed, since if both and are given the same color for every , the resulting coloring is an -coloring for which no vertex can be recolored. However, is not lower-bounded by a function of since for any , some tree satisfies and  [3]. In addition, unlike the maximum degree, the grundy number is NP-hard to compute [21].

Given a graph and an integer , it is NP-complete to decide if  [2]. Nevertheless, for every fixed , there is a linear-time algorithm to decide if the treewidth is at most (and find a tree decomposition) [4]. Graphs of treewidth , being -degenerate, are -mixing [8]. However, the best upper-bound known on the recoloring diameter is exponential. In Section 4, we prove that the recoloring diameter is polynomial for bounded treewidth graphs, a problem left open in [6].

###### Theorem 2.

For every graph , if , then is -mixing and its -recoloring diameter is at most .

Section 4 is devoted to a proof of Theorem 2, which is independent from Theorem 1. The quadratic upper bound on the recoloring diameter was known for chordal graphs [6], but its generalization to bounded treewidth graphs was left open. As shown in the case of chordal graphs [6] (which is a subclass of graphs of treewidth ), the mixing number is tight, and the recoloring diameter is tight up to a constant factor. The existence of a polynomial recoloring diameter in the case of -degenerate graph is still open and will be discussed in Section 6. A sketch of the proofs of Theorem 1 and 2 were published in the extended abstract of LAGOS’13 [5].

The last main results of this paper deal with cographs and distance-hereditary graphs. The class of cographs is the class of -induced free graphs, i.e. the class of graphs that do not contain a path on four vertices as an induced subgraph. By Theorem 1, we obtain the following:

###### Corollary 3.

For every cograph , if , then is -mixing and its -recoloring diameter is at most .

Indeed, the grundy number of cographs is equal to their chromatic number [14]. Recall that cographs are -free graphs. Can we generalize this result to the class of -free graphs for any fixed ? It is easy to answer negatively to this question by observing that complete bipartite graphs minus a matching (see Fig. 1) are -free graphs and that the mixing number of such graphs is arbitrarily large. We can build an ad-hoc -free graph with chromatic number which is not -mixing (see Fig. 2). In fact, we can even build a family of -free graphs that admit both a -coloring and a frozen -coloring, as follows. Take a clique , remove all edges , add for all a vertex adjacent to all the ’s except . We obtain a -coloring by setting for all and for all such that exists, and a frozen -coloring by setting and for all . Not all edges are necessary, but it is easier that way to verify that there is indeed no induced .

Note that, since the -recoloring diameter of the class of induced paths is quadratic [6], only graph classes excluding long paths can have a linear recoloring diameter. Corollary 3 ensures that -free graphs admit a linear recoloring diameter. So we raise the following question: does the class of -free graphs with mixing number have a linear recoloring diameter?

Using a slight generalization of cographs, we finally prove in Section 5 that distance-hereditary graphs admit a quadratic recoloring diameter.

###### Theorem 4.

For every distance-hereditary graph and every , the graph is -mixing and it recoloring diameter is at most .

Once again, since distance-hereditary graphs contain long paths, the upper bound on the recoloring diameter is optimal up to a constant factor. Since the mixing number of complete bipartite graph minus a matching is not bounded by a function of the chromatic number, neither is it the case for any graph class containing them, thus for comparability graphs, perfectly orderable graphs, and then perfect graphs, answering a question of [6]. Considering that comparability graphs form the smallest interesting superclass of distance-hereditary graphs, Theorem 4 is in some sense optimal with regards to the graph class, as it is optimal as to the bound on the recoloring diameter.

Finally note that all our results are also algorithmic. Indeed each proof can be adapted into a polynomial-time algorithm that will find a short recoloring sequence. The one exception is for bounded treewidth graphs. Indeed determining the treewidth of a graph is an -hard problem. Nevertheless, for every fixed , deciding whether the treewidth of the graph is at most (and if so, producing a corresponding tree decomposition) can be done in linear time [4].

## 2 Preliminaries

Let us first recall some classical definitions on sets. Let and be two subsets of . The set is the subset of elements such that . By abuse of notation, given a set and an element , denotes and will sometimes be denoted by . The size of is its number of elements.

Let be a graph. For any coloring of , we denote by the set of colors used by on the subgraph of . The neighborhood of a vertex , denoted by is the subset of vertices such that . The length of a path is its number of edges. The distance between two vertices and , denoted , is the minimum length of a path between these two vertices. When there is no path, the distance is infinite. The distance between two -colorings of is implicitely the distance between them in the recoloring graph . Let us first recall a classical result on recoloring.

###### Lemma 5.

If , any -coloring of can be transformed into any other by recoloring every vertex at most twice.

###### Proof.

Let be two colorings of . Assume is initially colored in . We plan to recolor into while recoloring each vertex at most twice. Let be the digraph on vertices with an arc if is currently colored in . Informally is an arc if the current color of prevents the recoloring of into its final color (in ). The coloring of is proper at any time: no two vertices are colored identically, so . The same argument holds for , so . Hence is a disjoint union of directed paths and of circuits.

We recolor every directed path as follows. Let be a directed path. Then , and we can recolor into its final color in . Then , and we recolor into its final in . We repeat that operation until is recolored. Now every vertex of the directed path is an isolated vertex in , since no two vertices are colored identically in .

Let be a circuit. Since , can be recolored with a free color. After this recoloring, we have , so becomes a directed path, which we recolor as such. We then recolor into . Now every vertex of circuit is an isolated vertex in . We repeat that operation until no circuit remains in . Since we already recolored every directed path and was initially a disjoint union of directed paths and circuits, the clique is now colored in . ∎

## 3 Mixing number and grundy number

This section is devoted to a proof of Theorem 1, which is derived from the following lemma.

###### Lemma 6.

Let be a graph on vertices, and . For any -coloring of and any grundy -coloring of , we have .

###### Proof.

Let us prove it by induction on . If , has no edge and in steps, we can transform into . Assume now that . For any integer and any coloring , is the set of vertices of color in . Iteratively on from to , we recolor the vertices of with the smallest color for which the coloring is still proper. The resulting coloring of is the greedy coloring relative to the order . Hence is an (at most) -coloring. In addition, , since no vertex is recolored twice. Since no vertex is colored with in and , we recolor vertices of with color . We then recolor vertices of with if needed. The resulting coloring satisfies . In addition, , since no vertex is recolored twice. Let us now prove that the induction hypothesis holds on with , , and . We have . Indeed, assume that there is an order on such that . Consider the order on . Every vertex of has a neighbor on (since is grundy), so the greedy coloring relative to needs colors for , a contradiction. We also have . Indeed, for the order on corresponding to , the greedy coloring of relative to requires at least colors. So we can apply the induction hypothesis on with , , and (the color is forgotten, thus a greedy coloring will start with color , and is an grundy coloring of ). This ensures that can be recolored in steps. Consequently, . ∎

Finally, we consider a graph on vertices, an integer , and two -colorings and of . By definition of the chromatic number, we know there exists a grundy -coloring of . Since, , Lemma 6 ensures that . However, finding a grundy -coloring of is NP-complete. For a polynomial-time algorithm, we can derive from a grundy coloring in at most steps, and apply Lemma 6 on and , to obtain that .

## 4 Bounded treewidth graphs

The aim of this section is to prove Theorem 2. A tree is a connected graph without cycles. To avoid confusion, its vertices are called nodes. A tree decomposition of is a tree such that:

• To every node of , we associate a bag .

• For every edge of , there is a node of such that both and are in .

• For every vertex , the set of nodes of whose bags contain forms a non-empty subtree in .

The size of a tree decomposition is the largest number of vertices in a bag of , minus one. The treewidth of is the minimum size of a tree decomposition of .

A chordal graph is a graph that admits a perfect elimination ordering: that is, the vertices of the graphs can be ordered in such a way that the neighborhood of any vertex in forms a clique. Any chordal graph admits a tree decomposition whose bags are the maximal cliques of .

Actually, any tree decomposition of a graph can be viewed as a chordal graph with vertex set that admits as a subgraph ( is a supergraph of ). Informally, we transform step-by-step any -coloring of a graph into a -coloring of a ”good” chordal supergraph with the same treewidth.

We first introduce particular tree decompositions, called complete tree decompositions. In such decompositions, all the bags have exactly the same size and any two adjacent bags differ on exactly one vertex. Two vertices are parents if their subtrees are, in some sense, adjacent. A -coherent coloring is a coloring where parents are colored identically, i.e. a coloring of the vertices that is compatible with the chordal supergraph corresponding to the complete tree decomposition.

The proof is divided into two parts. First we prove that the distance between -coherent colorings is linear. We then prove that any coloring can be transformed into a -coherent coloring with a quadratic number of recoloring steps as long as the number of colors is at least .

### 4.1 Families

A tree decomposition of a graph is -complete when every bag has size and any two adjacent nodes satisfy . In other words, for every edge of , there exists a vertex such that . For any subtree of , denotes . Let . The tree decomposition is the same tree as except that the bag of every node is , and that every edge of is contracted if . In Fig. 3, the full-line edges subtree is . The following remark is an immediate consequence of the definition of complete tree decomposition.

###### Remark 1.

Any connected subtree of an -complete tree decomposition is still -complete.

A baby is a vertex of that appears in exactly one bag , where is a leaf of . Note that all the neighbors of a baby are in . In Fig. 3, vertex is a baby.

###### Remark 2.

Let be an -complete tree decomposition. If is a baby then is -complete.

###### Proof.

Let be the unique node whose bag contains . Then the only modified bag in is . Let be the father of in . Since is complete, in , so the edge is contracted in . Therefore is exactly which is -complete by Remark 1. ∎

We first prove that every graph admits complete tree decompositions. Then we derive from it the notion of parents and family between vertices of .

###### Lemma 7.

For every graph , if then admits an -complete tree decomposition.

###### Proof.

By definition of , the graph admits a tree decomposition whose every bag has size at most . We can assume w.l.o.g. that no bag is contained in another in : if two adjacent nodes in verify , then the edge can be contracted.

We build inductively an -complete tree decomposition of such that every bag of is contained in a bag of .

If , then the tree decomposition consisting of a single node with bag is -complete.

If , then has at least two nodes since every vertex is contained in at least one bag. Let be a leaf of and be the neighbor of . Since no bag is contained in another in , there is a vertex in . Note that is a baby. Otherwise the subset of nodes whose bags contain would not be a subtree of since and is the unique neighbor of in . Let .

By induction hypothesis, admits an -complete tree decomposition where every bag of is contained in a bag of . So some node of satisfies . Since , some vertex of is not in . We consider built from by adding a leaf attached on whose bag is . Then is an -complete tree decomposition of with the required property with regards to . ∎

Let be a complete tree decomposition. Note that for every edge . Two vertices are -parents if there are two adjacent nodes of such that , and . In other words, vertices and are -parents if the subtree of the nodes containing in their bags and the subtree of the nodes containing in their bags do not intersect, but are connected by an edge ( in this case). When no confusion is possible we will use the term parents instead of -parents. Also note that the notion of parents is symmetric: if is a parent of then is a parent of . The family relation is the transitive closure of the parent relation. A family is a class of the family relation. In Fig. 3, the families are and . The partition of induced by the families is called the family partition. In Fig. 3, vertices and are parents.

###### Remark 3.

The family partition of any -complete tree decomposition exists and is unique. Each family contains exactly one vertex in every bag. So there are families, which are stable sets.

###### Proof.

By induction on . If has a single node , then no vertex has a parent. So each family is a single vertex. Assume has at least two nodes. Let be a leaf of and be its adjacent node. Note that the family partitions of are the extensions of those of . The vertices and are parents and is the unique parent of . Since is a leaf of , is still -complete by Remark 1.

By induction, contains exactly one vertex of every family of the unique family partition of . Since , and since is the unique parent of , we can uniquely extend the partition by adding in the family of . Besides, in there is exactly one vertex of each family. ∎

### 4.2 Coherent colorings

Let be an -complete tree decomposition of a graph . A coloring is -coherent (relatively to ) if for every that are parents, and for every bag and every , only is colored with in . Note that since parents are non-adjacent in the graph by Remark 3, coherent colorings can be proper. Note that a -coherent coloring is a proper -coloring which is in some sense canonical: given two -coherent colorings, they differ only up to a color permutation. Our recoloring algorithm consists in transforming any coloring into such a canonical coloring. Then we can transform any -coherent coloring into any other using the recoloring algorithm of the clique.

The subsection is organized as follows. First we define the notion of merging. Then we prove that the distance between -coherent colorings is linear. And we finally provide some recoloring lemmas regarding -coherent colorings. All these tools will be used in Section 4.3.

Let be a graph and be a stable set. The merged graph on is the graph where vertices of are identified into a vertex and is an edge if there exists a vertex such that is an edge. A coloring of the merged graph can be extended on the whole graph by coloring every vertex of with . For any stable sets with for any , the merged graph on is the graph obtained from by merging successively .

###### Remark 4.

Let be a stable set. Let be two colorings of the merged graph on and be their extended colorings. If can be transformed into by recoloring each vertex at most times, then can be transformed into by recoloring every vertex at most times.

###### Proof.

We just have to follow the recoloring process of into . If the recolored vertex is not , then perform the same recoloring in the extended graph. Otherwise, recolor the vertices of (one after the other) into the new color of in the extended graph. All the intermediate colorings are proper since is a stable set. ∎

Remark 4 formalizes an easy fact: when there is a set of a same color, then we can consider it as a single vertex.

###### Remark 5.

Let be an -complete tree decomposition, let be a stable set of that belongs to the same family and let be the merged graph on . If is connected, then for the tree obtained from by contracting any edge such that and differ only on vertices of , is an -complete tree decomposition of .

###### Proof.

By induction on .

If , and are actually and , so the result holds.

If , since is connected, for , and are parents. Let be the merged graph on and be the tree obtained from by contracting any edge such that and differ only on vertices of . The set of nodes of whose bags contain or forms a non-empty subtree of , so the same holds of . Then the tree is a tree decomposition of . The tree decomposition is still -complete since every bag of corresponds to (at least) a bag of , and any two adjacent nodes in correspond to two adjacent nodes in .

If , we consider a leaf of . We apply the induction hypothesis with : we obtain the graph and the -complete tree decomposition . Let be the vertex of corresponding to . Note that belongs to the same family as . Since is connected, so is . We apply the induction hypothesis on and with . The resulting graph and -complete tree decomposition are also the graph and tree decomposition that would have been obtained by merging directly on . ∎

###### Lemma 8.

Let . If every -coloring of can be transformed into a -coherent coloring with at most recolorings, then the -recoloring diameter of is at most .

###### Proof.

Let be two -colorings of . By assumption, there are two -coherent colorings and such that and .

Let us prove that . By definition, all the vertices of a same family are colored identically in . The same holds for . Let be the merged graph where every family is identified into a same vertex. By Remark 3, the family partition is unique, so both and are extensions of and colorings of . Every pair of vertices of have distinct colors in (and in ). So can be considered as a clique on vertices (since there are families). Lemma 5 and Remark 4 ensure that . Since , Lemma 8 holds. ∎

Let us first make some observations for the two forthcoming lemmas. Let be a tree and be a node of . We can consider that is rooted on . Then is the father of if is an edge and is not in the connected component of in . The tree rooted on , denoted by , is the connected component of in . Note that if is an -complete tree decomposition, then so is for any . Let us first prove some stability on -coherent colorings. This slightly technical lemma is at the core of the recoloring algorithm.

###### Lemma 9.

Let be an -complete tree decomposition rooted at and let be a node of distinct from . Let be a -coherent coloring where color does not appear in .
If a vertex of is colored with , every bag of contains a vertex colored with .

###### Proof.

Assume by contradiction that a node of does not contain a vertex colored with in its bag. Choose in such a way is as near as possible from in . Then the father of contains a vertex of color . The vertex is not in since . Let . We have since and is the father of . So and are parents. Since is -coherent, we have . But , a contradiction. ∎

###### Lemma 10.

Let be two integers with . Let be an -complete tree decomposition rooted on . Let be a -coherent -coloring where some color does not appear in .

Then by recoloring every vertex of at most once, we can obtain a -coherent -coloring where no vertex is colored with .

###### Proof.

Let us prove it by induction on . Given a subset of vertices of , two vertices are in the same -family if they are in the closure relation of the parents relation restricted to the vertices of (note that if the two notions coincide). For every ()-family , we merge all the vertices of . Since the coloring is -coherent, it makes sense: all the vertices of were colored identically. By Remark 5, the resulting tree decomposition is still -complete. By Remark 4, recoloring the resulting graph suffices: the resulting coloring will be -coherent in any case.

If , then the graph has no edge. Color can be eliminated by recoloring every vertex at most once since the graph is a stable set.

If , for every son of , we proceed as follows. If a vertex of is colored with then it is necessarily the vertex . We consider two cases depending on whether .

• Assume . Since is smaller than , by the induction hypothesis we can recolor without recoloring any vertex of (and then of ), so as to obtain a -coherent coloring with no vertex of color .

• Assume . By Remark 3, every node of contains exactly one vertex of the same family as . Since we merged on the families of , vertex belongs to every node of . Thus is an -complete tree decomposition of , and color does not appear on . We remove color from the set of available colors. Since is -coherent, it is in particular -coherent. Take a color that does not appear on . We apply the induction hypothesis on with , and color . Every vertex of has been recolored at most once, and by assumption, neither color nor appears on this set. We recolor in . Since , every vertex of has been recolored at most once, and color does not appear in .

By Remark 4, the resulting coloring is de facto -coherent. Every vertex has been recolored at most once, no vertex of has been recolored, and no vertex is colored in . ∎

### 4.3 Obtaining a V-coherent coloring

In order to prove Theorem 2, Lemma 8 ensures that we just have to transform any coloring into a -coherent coloring in at most steps. We will consider the vertices one after the other and we will try to obtain a coloring that is coherent when restricted to the vertices already treated. The recoloring algorithm is detailed in the following lemma:

###### Lemma 11.

Let be a -complete tree decomposition. For every -coloring of , there is a -coherent coloring such that .

###### Proof.

The proof consists in a recoloring algorithm. We treat vertices one after the other, considering vertices that have at most one parent not yet treated. In other words, we treat babies of the remaining tree-decomposition. Our invariant will ensure that, when is treated, the current coloring is -coherent. When a new vertex is treated, we just have to transform the current coloring in order to obtain a -coherent coloring. At the end of the procedure, the whole vertex set is treated, and then the current coloring is -coherent.

Let us now describe more formally the invariants. The set represents treated vertices at step . Initially, no vertex is treated, so . The coloring is the current -coloring at the end of step . Initially the coloring is , so . The invariants at the end of step are:

1. , and .

2. is a -complete tree decomposition of .

3. is an -coloring of obtained from by recoloring vertices of at most twice.

4. is -coherent.

We proceed iteratively on from to . Let be a leaf of and be a baby contained in . In Fig. 3, the node is a leaf of and is the corresponding baby. We want to add in . Denote by the set . By Remark 2 and since is a baby, is a complete tree decomposition. Thus (i) and (ii) are immediately verified. The following consists in proving (iii) and (iv).

A residual component of is a connected component of . Informally, a residual component is a subtree of the tree decomposition containing at least one treated vertex. A residual component of is a residual component containing a node adjacent to . Note that vertices which appear in a bag of such a residual component are included in . In Fig. 3, subtrees and are the residual components of in .

Let be the union of the residual components on . And let be the subtree induced by rooted on . Let us consider the graph restricted to the vertices of . Let be a color which does not appear in . Note that the coloring restricted to is -coherent. Indeed, the vertices of are in , and the coloring is -coherent.

By applying Lemma 10, can be transformed into a -coherent coloring of where no vertex is colored with . Every vertex of is recolored at most once. Note that since vertices of are not recolored, the obtained coloring is proper on the whole graph. Since is still in the clique tree, it means that no vertex of is in . So if two vertices of are parents, either they are both in or none is in . So the resulting coloring is -coherent.

At this point, the color has disappeared from and the coloring is -coherent. So all the members of the family of that are in can be recolored with , as the vertex itself. Every vertex is recolored at most once. Finally every vertex is recolored at most twice. So the resulting coloring satisfies conditions (iii) and (iv).

This operation is repeated until , that is, . When the last vertex is treated the coloring is -coherent by (iv). It follows from (iii) that to recolor from to , it suffices to recolor each vertex at most , where is the smallest such that . Thus, on the whole, it suffices to make recolorings. Actually, the analysis can be slightly improved. Indeed, the vertex treated at step is recolored at most once (since vertices of are not recolored in Lemma 10). Therefore, every vertex is recolored at most times, which finally ensures that . ∎

Note that the proof is totally algorithmic and runs in polynomial time (for a fixed number of colors).

## 5 Cographs and distance-hereditary graphs

In this Section, the notion of modules will be essential. Given a graph , a subset of vertices is a module if, for every vertex then is adjacent to either every vertex of or none of them. A subset of vertices is a strong module if and for every module of , and are either disjoint or contained one in the other. In this section, the total order on the colors is the standard order on the integers.

###### Remark 6.

For every graph, any three strong modules and such that satisfy .

###### Proof.

Assume by contradiction that three strong modules such that satisfy . There is no edge between any vertex of and . Indeed otherwise must be connected to every vertex of since is a module. And thus , a contradiction.

Therefore is a module of . Indeed, they have the same neighborhood in since is a module and the same neighborhood in since there is no edge beween and . Though, strictly intersects with , a contradiction since is a strong module. ∎

###### Remark 7.

For every graph , every vertex belongs to at most distinct strong modules.

###### Proof.

Since every strong module containing intersects any other on , all of them are included the ones into the others by definition of strong modules. Since the chromatic number of a module is at most , Remark 6 ensures that is contained in at most strong modules. ∎

### 5.1 Cographs and quasi-cographs

A graph is a cograph [19] if it does not contain induced paths of length . Equivalently, a graph is a cograph if:

• is a single vertex.

• Or can be partitionned into such that and are cographs and there is no edge between any vertex of and any vertex of .

• Or can be partitionned into such that and are cographs and every vertex of is adjacent to every vertex of (such an operation is called a join).

Note in particular that in the two last constructions, both subsets and are modules. In addition, in the second (resp. third) construction, is a strong module of iff it is not the disjoint union (resp. join) of two cographs. It follows that in a cograph, all the strong modules are a single vertex or the disjoint union of strong modules, or the join of strong modules. The cographs have been introduced in 1971 and have been extensively studied (see [1]).

A coloring of a cograph is said to be modular if for every strong module of that is the disjoint union of strong modules , the coloring uses a set of exactly colors on the set , and every is colored in with the first colors in . Partially joining a clique to a graph means taking a non-empty subset of and joining it to the graph.

A quasi-cograph rooted in , where is a cograph, is the graph obtained by partially joining cliques to modules of such that no two ’s strictly overlap. By partially joining, we mean that some vertices of the clique are totally connected to the module and others are not connected. Note that may be equal to , so cographs are in particular quasi-cographs rooted in themselves. Note also that two ’s might be identical. In other words, a quasi-cograph is obtained from a cograph by adding pending cliques on non-strictly overlapping modules of the cograph (see Figure 4). Given a subset of vertices of , the vertices rooted in are the vertices of the quasi cograph which are not in and connected to a vertex of . By extension, a modular coloring of a quasi-cograph is a coloring of it whose restriction to the underlying cograph is modular.

In order to prove the bounds on the mixing numbers of cographs and distance-hereditary graphs, we will first prove a few recoloring properties on quasi-cographs. Before stating the recoloring results, let us recall interesting properties of modules in cographs.

###### Claim 1.

A cograph that admits no non-trivial strong module is either a clique or a stable set.

###### Proof.

By induction on .

• If is a single vertex, the result holds.

• If is the disjoint union of two cographs and . A non-trivial strong module of (resp. ) is a strong module of , thus by the induction hypothesis, both and are either a clique or a stable set. Since is not a stable set, assume w.l.o.g. that is a clique (of size at least ). Then is a strong module of (indeed a module containing a strict subset of does not contain a vertex of ), a contradiction.

• If is the join of two cographs and . Similarly, we can assume that is a stable set, which implies that is a strong module of , a contradiction.

We start with an easy lemma:

###### Lemma 12.

Let be a quasi-cograph rooted in and . Every -coloring of can be recolored into a modular coloring with by recoloring every vertex at most times, while using no color on beside .

###### Proof.

Then is a graph obtained by partially joining cliques to modules of such that no two ’s strictly overlap.

Let be a smallest strong module of such that is not modularly colored. Thus every maximal strong module of strictly included in is modularly colored: we consider these strong modules to behave as a clique (where each color class corresponds to a single vertex) which is possible by Remark 4 (all the vertices of the same color class are merged which ensure that any recoloring is still a modular coloring for these modules). If was the join of strong modules, it is now a clique and its coloring is necessarily modular. Then was the disjoint union of cliques . Since is a strong module, every that intersects but does not contain it is strictly included in . Since is a module, if is strictly included in then is either strictly included in some , or is a union of ’s.

Let be a minimal included in that is not minimally colored, or itself if there is no such . The ’s strictly included in are considered to behave as cliques (again, where each color class is merged into a single vertex). We denote the resulting (at least two) disjoint cliques in . Note that all the cliques partially joined to a strict subset of are partially joined to some strictly included in and thus to a subset of some . Let be the colors used on , in that order (i.e. with ). For every from to , for each with , we pick a vertex that is colored with a color larger than , if any.

We then recolor if needed the pending cliques on some subset of


text:
# Executing a command after a package has been loaded

In my previous question I ended up with

\DeclareMathSymbol{:}{\mathpunct}{operators}{"3A}

But now I'm using the fontspec package which redefines : with \AtBeginDocument itself. So as my own definition comes before fontspec is loaded, even putting it in \AtBeginDocument won't help.

Is there a way to say “Execute this after fontspec has loaded!” or “Execute this at the very end of \AtBeginDocument!”?

-

According to the documentation of afterpackage this should work

\usepackage{afterpackage}
\AfterPackage{fontspec}{%
\AtBeginDocument{\DeclareMathSymbol{:}{\mathpunct}{operators}{"3A}}%
}

-
Great, thank you! –  canaaerus Jul 24 '12 at 9:53

There's also the scrlfile package from KOMA-script:

\usepackage{scrlfile}
\AfterPackage{fontspec}{%
\AtBeginDocument{\DeclareMathSymbol{:}{\mathpunct}{operators}{"3A}}%
}

It has a bunch of other useful commands.

-
Actually I do use scrartcl. So that clears up why I got “\AfterPackage already defined” on \usepackage{afterpackage}. –  canaaerus Jul 24 '12 at 11:58

Put it in \AtBeginDocument after you load fontspec any commands saved by that command are executed in order, so if you do it that way your saved commands will be executed after the packages.

-
Well, that is exactly what I didn't want to do. Actually I'm issuing \DeclareMathSymbol in my document class, which I then \dump with the rest of the preamble to speed up compilation. fontspec can not be dumped, so I put it right before \begin{document}. –  canaaerus Jul 24 '12 at 9:39
ah well an alternative is to patch \document to add your hook stuff just after it runs \@begindocumenthook –  David Carlisle Jul 24 '12 at 9:41

format: plain


text:
(50g) Bernoulli polynomials
12-17-2018, 07:03 PM
Post: #3
 John Keith Senior Member Posts: 776 Joined: Dec 2013
RE: (50g) Bernoulli polynomials
(12-17-2018 06:07 PM)DavidM Wrote:  One very easy way to accommodate the possibility of a varying number of arguments is to place them in a list { } before invoking the program. Placing a list of items on the stack is actually very easy (only one shifted key more than individually loading them). Your program then simply needs to execute LIST→ instead of DEPTH to determine how many arguments were given.

I believe this is a small adjustment to make in comparison to the benefits to the user of not having to clear the stack first.

I second this method. One can also begin the program with

Code:
 IF DUP TYPE 5. SAME THEN OBJ\->... (do whatever with multiple args) ELSE... (use program-supplied defaults)

to allow either a single argument with the program supplying defaults, or some or all arguments supplied by the user.

For example compare UTPN on the HP 50 with NORMALD_CDF, its rough equivalent on the Prime.
 « Next Oldest | Next Newest »

 Messages In This Thread (50g) Bernoulli polynomials - peacecalc - 12-17-2018, 05:31 PM RE: (50g) Bernoulli polynomials - DavidM - 12-17-2018, 06:07 PM RE: (50g) Bernoulli polynomials - John Keith - 12-17-2018 07:03 PM RE: (50g) Bernoulli polynomials - DavidM - 12-17-2018, 08:37 PM RE: (50g) Bernoulli polynomials - ttw - 12-17-2018, 09:17 PM RE: (50g) Bernoulli polynomials - peacecalc - 12-17-2018, 10:03 PM RE: (50g) Bernoulli polynomials - ijabbott - 12-17-2018, 11:58 PM RE: (50g) Bernoulli polynomials - peacecalc - 12-22-2018, 11:06 PM RE: (50g) Bernoulli polynomials - John Keith - 12-23-2018, 07:58 PM RE: (50g) Bernoulli polynomials - peacecalc - 12-29-2018, 02:18 PM RE: (50g) Bernoulli polynomials - Albert Chan - 12-29-2018, 03:52 PM RE: (50g) Bernoulli polynomials - DavidM - 12-29-2018, 04:40 PM RE: (50g) Bernoulli polynomials - John Keith - 12-29-2018, 05:54 PM RE: (50g) Bernoulli polynomials - peacecalc - 12-30-2018, 01:44 PM RE: (50g) Bernoulli polynomials - ttw - 01-02-2019, 11:13 PM RE: (50g) Bernoulli polynomials - peacecalc - 01-03-2019, 10:20 AM

User(s) browsing this thread: 1 Guest(s)


text:
Seminari de Geometria Algebraica de Barcelona
 UB UPC UAB
 Index anual Seminari 2017/2018 Seminari 2016/2017 Seminari 2015/2016 Seminari 2014/2015 Seminari 2013/2014 Seminari 2012/2013 Seminari 2011/2012 Seminari 2010/2011 Seminari 2009/2010 Seminari 2008/2009 Seminari 2007/2008 Seminari 2006/2007 Seminari 2005/2006 Seminari 2004/2005 Seminari 2003/2004 Seminari 2002/2003 Seminari 2001/2002 Contacta amb els organitzadors: Joaquim Roé Martí Lahoz
Seminari de Geometria Algebraica 2018/2019

Conferenciant

Títol Data i hora
ARCADES Doctoral School II and ESR Days 3 a 7 de setembre, IMUB
Constantin Shramov
Steklov Math Inst & NRU HSE
Moscou, Rússia

Contact:
ignasi.mundet at ub.edu
Automorphisms of Kaehler manifolds I will survey various results about finite groups acting by automorphisms and birational automorphisms of Kaehler manifolds. I will show that in many cases such groups enjoy the Jordan property, similar to subgroups of general linear groups.
The talk is based on joint works with Yu. Prokhorov.
Martín Sombra
ICREA - UB
The zero set of the independence polynomial of a graph In statistical mechanics, the independence polynomial of a graph G arises as the partition function of the hardcore lattice gas model on G. The distribution of the zeros of these polynomials when G→∞ is relevant for the study of this model and, in particular, to the determination of its phase transitions. In this talk, I will review the known results on the location of these zeros, with emphasis on the case of rooted regular trees of fixed degree and varying depth k ≥ 0. Our main result states that for these graphs, the zero sets of their independence polynomials converge as k→∞ to the bifurcation measure, in the sense of DeMarco, of a certain family of dynamical systems on the Riemann sphere.
This is ongoing work with Juan Rivera-Letelier (Rochester)
Divendres 28 de setembre, 15h, Aula T2, FMI-UB
Alberto F. Boix
Ben-Gurion U. of the Negev
Beer-Sheva, Israel

Contact:
szarzuela at ub.edu
A Characteristic Free Approach to Finite Determinacy Finite determinacy for mappings has been classically thoroughly studied in numerous scenarios in the real and complex-analytic category and in the differentiable case. It means that the map-germ is determined, up to a given equivalence relation, by a finite part of its Taylor expansion. The equivalence relation is usually given by a group action and the first step is always to reduce the determinacy question to an “infinitesimal determinacy”, i.e. to the tangent spaces at the orbits of the group action.
The goal of this talk is to formulate a universal approach to finite determinacy in arbitrary characteristic, not necessarily over a field, for a large class of group actions; along the way, we introduce the notion of “pairs of (weak) Lie type”, which are groups together with a substitute for the tangent space at the unit element, such that the group is locally approximated by its tangent space, in a precise sense. This construction may be regarded as a sort of replacement of the exponential/logarithmic maps and is of independent interest. In this generality we establish the “determinacy versus infinitesimal determinacy” criteria, a far reaching generalization of numerous classical and recent results, together with some new applications.
The content of this talk is based on joint work with Gert–Martin Greuel (Universität Kaiserslautern, Germany) and Dmitry Kerner (Ben–Gurion University of the Negev, Israel)
Divendres 5 d'octubre, 15h, Aula T2, FMI-UB
Roberto Gualdi
U. Bordeaux - UB - CRM

Contact:
sombra at ub.edu
Height of cycles in toric varieties We present in this talk some relations between suitable heights of cycles in toric varieties and the combinatorics of the defining Laurent polynomials. To do this, we associate to any Laurent polynomial f with coefficients in an adelic field two families of concave functions on a certain real vector space: the upper functions and the Ronkin functions of f. For the choice of an adelic semipositive toric metrized divisor D, we give upper bounds for the D-height of a complete intersection in a toric variety in terms of the upper functions of the defining Laurent polynomials. In the one-codimensional case, we prove an exact formula relating the D-height of a hypersurface to the Ronkin function of the associated Laurent polynomial, generalizing the well-known equality for the canonical case. Our approach involves mixed integrals, Legendre-Fenchel duality and other notions from convex geometry.
Divendres 19 d'octubre, 15h, Aula T2, FMI-UB
Francisco Presas

Contact:
ignasi.mundet at ub.edu
Homotopy type of the space of smooth embeddings of $$\Large{\mathbb{S}}^1$$ in $$\Large{\mathbb{R}}^4$$ via Engel geometry. We introduce the space of horizontal embeddings for the standard Engel distribution in the Euclidean 4-space. We prove that the space of smooth embeddings of the circle into R⁴ is simply connected (classical result), by checking that the space of horizontal embeddings has homotopy type very related to the space of smooth embeddings (they are related by an h-principle). We extend the method to sketch the computation of the $$\pi_2$$ of that space showing that is Z$$\oplus$$Z (more modern result). We finally comment on work in progress further generalizing the techniques by using Manifold calculus to try to compute the whole homotopy type of this space.
This is joint work with E. Fernández and X. Martínez-Aguinaga.
Divendres 26 d'octubre, 15h, Aula T2, FMI-UB
Pedro D. González Pérez
ICMAT - UCM, Madrid

Contact:
The valuative tree is a projective limit of Eggers-Wall trees Consider a germ C of reduced curve on a smooth germ S of complex analytic surface. Assume that C contains a smooth branch L. Using the Newton-Puiseux series of C relative to any coordinate system (x,y) on S such that L is the y-axis, one may define the Eggers-Wall tree ΘL(C) of C relative to L. Its ends are labeled by the branches of C and it is endowed with three natural functions measuring the characteristic exponents of the previous Newton-Puiseux series, their denominators and contact orders. The main objective of this paper is to embed canonically ΘL(C) into Favre and Jonsson's valuative tree of real-valued semivaluations of S up to scalar multiplication, and to show that this embedding identifies the three natural functions on ΘL(C) as pullbacks of other naturally defined functions on the valuative tree. As a consequence, we prove an inversion theorem generalizing the well-known Abhyankar-Zariski inversion theorem concerning one branch: if L' is a second smooth branch of C, then the valuative embeddings of the Eggers-Wall trees ΘL'(C) and ΘL(C) identify them canonically, their associated triples of functions being easily expressible in terms of each other. We prove also that the valuative tree is the projective limit of Eggers-Wall trees over all choices of curves C. Joint work with Evelia García Barroso and Patrick Popescu-Pampu.
Divendres 9 de novembre, 15h, Aula T2, FMI-UB
Joana Cirici
UB
A Dolbeault cohomology theory for almost complex manifolds In this talk I will survey recent joint work with Scott Wilson which extends Dolbeault cohomology to all almost complex manifolds, and generalizes some foundational results for compact Kähler manifolds to the non-integrable setting. I will also explain Lie-algebra analogues of the theory which provide useful computational tools for compact Lie groups and nilmanifolds.
Divendres 16 de novembre, 15h, Aula T2, FMI-UB
Diletta Martinelli
School of Mathematics
Edinburgh, Escòcia (UK)

Contact:
marti.lahoz at ub.edu
On the geometry of contractions of the Moduli Space of sheaves of a K3 surface I will describe how recent advances have made possible to study the birational geometry of hyperkaehler varieties of K3-type using the machinery of wall-crossing and stability conditions on derived categories as developed by Tom Bridgeland. In particular Bayer and Macrì relate birational transformations of the moduli space M of sheaves of a K3 surface X to wall-crossing in the space of Bridgeland stability conditions Stab(X). I will explain how it is possible to refine their analysis to give a precise description of the geometry of the exceptional locus of any birational contractions of M.
Divendres 23 de novembre, 15h, Aula T2, FMI-UB
Bernd Sturmfels
Max Plank Institut Leipzig, Alemanya

Contact:
cdandrea at ub.edu
Moment Varieties of Polytopes The moments of the uniform distribution on a convex polytope are rational functions in its vertex coordinates. We study the projective varieties parametrized by these moments. This is work with Kathlen Kohn and Boris Shapiro. On our journey, we encounter Hankel determinantal ideals, splines, cumulants, multisymmetric functions, and invariants of nonreductive groups. While moment varieties are complicated, they offer many nice open problems. Article
Dilluns 26 de novembre, 15h, aula T1, FMI-UB
Vincenzo Antonelli
Politecnico di Torino, Itàlia

Contact:
miro at ub.edu
Ulrich bundles on Hirzebruch surfaces Ulrich bundles on a projective variety are vector bundles that admit a completely linear resolution as sheaves on the projective space. They carry many interesting properties and they are the simplest one from the cohomological point of view. In this talk we characterize Ulrich bundles of any rank on polarized rational ruled surfaces over P¹. We show that every Ulrich bundle admits a resolution in terms of line bundles. Conversely, given an injective map between suitable totally decomposed vector bundles, we show that its cokernel is Ulrich if it satisfies a vanishing in cohomology. Finally we discuss some particular cases and we construct examples of indecomposable Ulrich bundles.
Divendres 30 de novembre, 15h, Aula T2, FMI-UB
Enrico Carlini
Politecnico di Torino, Itàlia

Contact:
alessandro.oneto at upc.edu
Hilbert function of double points Hilbert functions of zero dimensional schemes, reduced or not, play a crucial role in many areas of mathematics: from Waring ranks of forms to identifiability of tensors. However, while we have a very good understanding of the reduced case, we know very little in the not reduced case. In this talk we will explore the situation with a special focus to double points in the plane.
Divendres 30 de novembre, 16h, Aula T2, FMI-UB
FACARD 2019 Workshop 16 a 18 de gener, IMUB
Laura Brustenga
UAB
Relative clusters for smooth families In the talk, we will discuss a generalisation of clusters of points to the relative setting. When the family is smooth, we are able to show that relative clusters form a representable functor. We will recall the construction of Kleiman's iterated blow-ups, which are the representing schemes for the absolute case. Thereafter we will focus on and work out an explicit example of length two relative clusters. The example is geometric and interesting in its own, but hopefully, it will also share some insight about the general situation.
Divendres 1 de febrer, 15h, Aula T2, FMI-UB
Elba Garcia-Failde
IPHT (CNRS) París-Saclay, França

Contact:
carles.casacuberta at ub.edu
Simple maps, topological recursion and a new ELSV formula In this talk, we call ordinary maps a certain type of graphs embedded on surfaces, in contrast to fully simple maps, which we introduce as maps with non-intersecting disjoint boundaries. It is well-known that the generating series of ordinary maps satisfy a universal recursive procedure, called topological recursion (TR). We propose a combinatorial interpretation of the important and still mysterious symplectic transformation which exchanges x and y in the initial data of the TR (the spectral curve). We give elegant formulas for the disk and cylinder topologies which recover relations already known in the context of free probability. For genus zero we provide an enumerative geometric interpretation of the so-called higher order free cumulants, which suggests the possibility of a general theory of approximate higher order free cumulants taking into account the higher genus amplitudes.
We also give a universal relation between fully simple and ordinary maps through double monotone Hurwitz numbers, which can be proved either using matrix models or bijective combinatorics. In particular, we obtain an ELSV-like formula for double strictly monotone Hurwitz numbers with ramification profile (2,...,2) over 0 and arbitrary one over .
Divendres 8 de febrer, 15h, Aula T2, FMI-UB
Marco Gualtieri
University of Toronto, Canadà

Contact:
eva.miranda at upc.edu
The potential of generalized Kahler geometry Since the introduction of generalized Kähler geometry in 1984 by Gates, Hull, and Roček in the context of two-dimensional supersymmetric sigma models, we have lacked a general understanding of the degrees of freedom inherent in the geometry. In particular, the description of a usual Kähler structure in terms of a complex manifold together with a local Kähler potential function is not available for generalized Kähler structures, despite many positive indications in the literature over the last decade. I will explain how holomorphic Poisson geometry may be used to solve this problem and to obtain new constructions of generalized Kähler metrics.
Divendres 15 de febrer, 15h, Aula T2, FMI-UB
Paula Escorcielo
Universidad de Buenos Aires
Argentina

Contact:
cdandrea at ub.edu
A version of Putinar's Positivstellensatz for cylinders Let f be a polynomial in n variables with real coefficients. Assume f is positive (non-negative) in a basic closed semialgebraic set S, a certificate of the positivity (non-negativity) of f in S is an expression that makes evident this fact. For example, Hilbert's 17-th problem states that if a polynomial is non-negative in Rn, it can be written as a sum of squares of rational functions, which is a certificate of the non-negativity of f in Rn. It is well-known that Krivine's Positivstellensatz (which states necessary and sufficient conditions for a polynomial system of equations and inequations to have no solution in Rn) implies Hilbert's 17-th problem.
There are also other versions of Positivstellensatz, which hold on particular situations. For instance, Putinar's Positivstellensatz states that given g1, ..., gs polynomials in n variables with real coefficients such that the quadratic module M(g1, ..., gs) generated by g1, ..., gs is archimedean, every polynomial f which is positive on the basic closed semialgebraic subset S of Rn where g1, ..., gs are non-negative, belongs to M(g1, ..., gs). The archimedeanity assumption on M(g1, ..., gs) implies that the set S is compact.
In this talk, we will present a version of Putinar's Positivstellensatz in the case that the underlying basic closed semialgebraic set is not compact but a cylinder of type SxR.
This is a joint work with Daniel Perrucci.
Dilluns 18 de febrer, 15h, aula T2, FMI-UB
Thomas Strobl
Université Claude Bernard, Institut Camille Jordan, Lyon 1, França

Contact:
eva.miranda at upc.edu
The universal Lie ∞-algebroid of a singular foliation We associate a Lie ∞-algebroid to every resolution of a singular foliation, where we consider a singular foliation as a locally generated 𝒪-submodule of vector fields on the underlying manifold closed under Lie bracket, where 𝒪 is the ring of smooth, holomorphic, or real analytic functions. The choices entering the construction of this Lie ∞-algebroid, including the chosen underlying resolution, are unique up to homotopy and, moreover, every other Lie ∞-algebroid inducing the same foliation or any of its sub-foliations factorizes through it in an up-to-homotopy unique manner. We thus call it the universal Lie ∞-algebroid of the singular foliation. For real analytic or holomorphic singular foliations, it can be chosen, locally, to be a Lie n-algebroid for some finite n. If time permits we mention how to apply this construction to the realm of geometrical invariants and/or the construction of gauge theories.
This is joint work with Camille Laurent-Gengoux and Sylvain Lavau.
Divendres 22 de febrer, 15h, Aula T2, FMI-UB
Yairon Cid Ruiz
UB
Saturated special fiber ring and rational maps The idea of studying rational maps by looking at the syzygies of the base ideal is a relatively new idea that has now become an important research topic. In this talk, we will discuss some recent results that lead to birationality criteria and formulas for the degree of rational maps that depend on the algebraic properties of the syzygies of the base ideal. Mainly, we will introduce a new algebra called «saturated special fiber ring» and we will discuss its relations with the degree and birationality of rational maps between irreducible projective varieties. Time permitting, we will also discuss some results in the problem of specializing the coefficients of a rational map.
This talk is based on joint works with Laurent Busé and Carlos D’Andrea and with Aron Simis.
Divendres 1 de març, 15h, Aula T2, FMI-UB
Martin-Luther-Universität Halle, Alemanya
Multiplicities of jumping points for mixed multiplier ideals In this talk I want to present a systematic study of the multiplicity of the jumping points associated to the mixed multiplier ideals of a family of ideals in a complex surface with rational singularities. In particular we study the behaviour of the multiplicity by small perturbations of the jumping points. We also introduce a Poincaré series for mixed multiplier ideals and prove its rationality. If time allows, we would present some results about which topological information can be deduced from the jumping walls.
This is a joint work with Maria Alberich-Carramiñana, Josep Àlvarez Montaner and Víctor González Alonso.
Divendres 15 de març, 15h, Aula T2, FMI-UB
Nick Vannieuwenhoven
Katholieke Universiteit Leuven, Bèlgica

Contact:
alessandro.oneto at upc.edu
Geometry of the tensor rank decomposition The tensor rank decomposition or CPD expresses a tensor as a minimum-length linear combination of elementary rank-1 tensors. It has found application in fields as diverse as algebraic statistics, psychometrics, chemometrics, signal processing and machine learning, mainly for data analysis purposes. In these applications, the theoretical model is oftentimes a low-rank CPD and the elementary rank-1 tensors are usually the quantity of interest. However, in practice, this mathematical model is corrupted by measurement or sampling errors. In this talk, we will investigate the sensitivity of the CPD using techniques from algebraic and differential geometry.
Divendres 22 de març, 15h, Aula T2, FMI-UB
Jarosław Buczyński
Uniwersytet Warszawski - IMPAN, Polònia

Contact:
jroe at mat.uab.cat
Strassen's additivity of tensor rank for small three-way tensors For a tensor $$T\in A \otimes B \otimes C$$ (for vector spaces $$A$$, $$B$$ and $$C$$) the tensor rank of $$T$$ is the minimal number of simple tensors such that $$T$$ is the sum of those simple tensors. In this talk we address the problem of the additivity of the tensor rank. That is for two independent tensors we study if the rank of their direct sum is equal to the sum of their individual ranks. A positive answer to this problem was previously known as Strassen's conjecture until recent counterexamples were proposed by Shitov. The latter are not very explicit, and they are only known to exist asymptotically for very large tensor spaces. We show that for some small tensors the additivity holds. For instance, if the rank of one of the tensors is at most 6, then the additivity holds. Or, if one of the tensors lives in $$\mathbb{C}^k \otimes \mathbb{C}^3 \otimes \mathbb{C}^3$$ for any $$k$$, then the additivity also holds.
Based on a joint work with Elisa Postinghel and Filip Rupniewski.
Divendres 22 de març, 16h, Aula T2, FMI-UB
Patricio Almirón

Contact:
maria.alberich at upc.edu
On the quotient of Milnor and Tjurina number Two of the main invariants of plane curves singularities are Milnor number μ, of topological nature, and Tjurina number τ, of analytical nature. In 2017 A. Dimca and G.M. Greuel posed the following question:
Is it true that for any isolated plane curve singularity we have μ/τ<4/3?
In this talk I will present a partial answer to this question in the case of semi-quasihomogeneus singularities (joint work with G. Blanco) which constitute a new evidence to believe in a positive answer to Dimca and Greuel's question in the general case.
Divendres 29 de març, 15h, Aula T2, FMI-UB
Joan Carles Naranjo
Universitat de Barcelona
Hyperelliptic Jacobians and Isogenies We mainly consider abelian varieties isogenous to hyperelliptic Jacobians. In the first part of the talk we will prove that a very general hyperelliptic Jacobian of genus $$g\geq 4$$ is not isogenous to a non-hyperelliptic Jacobian. As a consequence we will obtain that the Intermediate Jacobian of a very general cubic threefold is not isogenous to a Jacobian. Another corollary is that the Jacobian of a very general $$d$$-gonal curve of genus $$g\geq 4$$ is not isogenous to a different Jacobian.

In the second part we will consider a closed subvariety $$\mathcal Y \subset \mathcal A_g$$ of the moduli space of principally polarized varieties of dimension $$g\geq 4$$. We will show that if a very general element of $$\mathcal Y$$ is dominated by the Jacobian of a curve $$C$$ and $$\dim \mathcal Y\geq 2g$$, then $$C$$ is not hyperelliptic. In particular, if the general element in $$\mathcal Y$$ is simple, its Kummer variety does not contain rational curves. Finally, if time permits, we will show that a closed subvariety $$\mathcal Y\subset \mathcal M_g$$ of dimension $$2g-1$$ such that the Jacobian of a very general element of $$\mathcal Y$$ is dominated by a hyperelliptic Jacobian is contained either in the hyperelliptic or in the trigonal locus.

These results have been obtained in collaboration with G.P. Pirola and can be found in arXiv:1705.10154v2 or https://doi.org/10.1016/j.aim.2018.07.025.
Divendres 5 d'abril, 15:10h, Aula T2, FMI-UB
Federico Caucci
Università di Roma 1 La Sapienza, Itàlia

Contact:
marti.lahoz at ub.edu
Derived invariants arising from the Albanese map Given a smooth complex projective variety, it is natural to ask which geometric information are preserved under derived equivalence. Namely, if two varieties have equivalent derived categories, what can we say about their geometry? We prove a general result in this direction: the derived invariance of the cohomology ranks of pushforward under the Albanese map of the canonical line bundle (twisted with elements of the Picard variety). In the case of maximal Albanese dimension this settles conjectures of Popa and Lombardi-Popa, including the derived invariance of the Hodge numbers $$h^{0,j}$$.
This is a joint work with G. Pareschi.
Divendres 26 d'abril, 15:10h, Aula T2, FMI-UB
Hóa Trần Quang
IMUB and Hue University, Vietnam
Geometry of rational maps via syzygies The study of rational maps is of theoretical interest in algebraic geometry and commutative algebra, and of practical importance in geometric modeling. In particular, rational maps in low dimension, typically parameterizations of curves and surfaces embedded in the projective space of dimension 3, are applied to shape modeling using computer-aided design methods for curves and surfaces in geometric modeling. Therefore, it is of vital importance to have a detailed knowledge of the geometry of these parametric representations.

In this talk, I will describe how geometric properties of a given rational map between projective spaces can be extracted from the syzygies of its defining homogeneous polynomials. Firstly, I will present our recent results on bounding the number of one-dimensional fibers of a rational map from $$\mathbb{P}^2$$ to $$\mathbb{P}^3$$. Secondly, I will discuss the effective criteria of birationality for dominant rational maps from $$\mathbb{P}^1\times \mathbb{P}^1$$ to $$\mathbb{P}^2$$.
Divendres 3 de maig, 15:10h, Aula T2, FMI-UB
Marcin Dumnicki
Uniwersytet Jagielloński w Krakowie, Polònia

Contact:
jroe at mat.uab.cat
Bound for Waldchmidt constants I will define the Waldschmidt constant of a homogeneous ideal $$I$$ to be the limit of the sequence $$a(I^{(m)})/m$$, where $$a(J)$$ is the least degree of a non-zero form in $$J$$, and $$I^{(m)}$$ is the symbolic power of $$I$$. I focus on bounds on Waldschmidt constant. Bounding from below usually requires methods, which can prove emptiness of some linear systems. I will recall some general results, as well as some close bounds for points and lines in projective spaces. Bounds from above are less known, but I will introduce one new invariant (asymptotic Hilbert polynomial) and use it to find good upper bounds.
Divendres 10 de maig, 15:10h, Aula T1, FMI-UB
Sascha Timme
Technische Universität Berlin, Alemanya

Contact:
piotr.zwiernik at upf.edu
3264 Conics in a Second Enumerative algebraic geometry counts the solutions to certain geometric constraints. Numerical algebraic geometry determines these solutions for any given instance. In this talk I want to illustrate how these two fields complement each other. The focus lies on the 3264 conics that are tangent to five given conics in the plane. I will illustrate tools and techniques used in numerical algebraic geometry and how we used these to find a fully real instance of this classic problem. This is joint work with P. Breiding and B. Sturmfels.
Divendres 17 de maig, 15:10h, Aula T2, FMI-UB
Juan Margalef
UPC
Parametrized theories: a way towards General Relativity What does it mean to have a degree of freedom at the boundary? In general relativity, it is important to answer this question in order to try to compute the entropy of a Black Hole. Spoiler alert: the answer is unclear. Nonetheless, we have tried to understand such question in simpler systems focusing on its geometric features. In that talk, I will take a tour through some of the theories that we have studied in order to answer this and similar questions, namely some field theories coupled to point masses, some parametrized theories and, of course, the theory of general relativity itself.
Divendres 24 de maig, 15:10h, Aula T1, FMI-UB
Francesco Cannas Aghedu
Università di Cagliari, Itàlia

Contact:
eva.miranda at upc.edu
Balanced metrics on the blow-up of C² at the origin An interesting open question in Kähler geometry is the characterization of projectively induced Kähler metrics. An important class of projectively induced Kähler metrics are the so called balanced metrics in the sense of Donaldson S. (Scalar curvature and projective embeddings. I. J. Diff. Geom. 59, 479-522 (2001)). This talk is a report of two works: On the balanced condition for the Eguchi-Hanson metric (J. of Geom. and Phy. 137, (2019), 35-39) and the second one joint with Andrea Loi: The Simanca metric admits a regular quantization (arXiv:1809.04431).
In particular, after a brief introduction to Balanced metrics, we see the blowing-up operation and we introduce two important complete Kähler metrics defined on the blow-up of C² at the origin: the celebrated Simanca metric and the Eguchi-Hanson metric. The Simanca metric is an important example (both from mathematical and physical point of view) of non homogeneous complete, zero constant scalar curvature metric. The Eguchi-Hanson metric is a well-known example of non homogeneous complete, Ricci-flat Kähler metric. In this talk we discuss on the balanced condition for these two Kähler metrics and their consequences.
Divendres 7 de juny, 15:10h, Aula T1, FMI-UB
Roberto Rubio
UAB
An introduction to generalized geometry Generalized geometry is an approach to geometric structures pioneered by Hitchin in 2003. In this talk I will focus on generalized complex geometry, as developed by Gualtieri, in order to introduce the main ideas and definitions, some of which are borrowed from Dirac geometry, such as the Dorfman bracket, or the concept of a Courant algebroid. I will try to illustrate the threefold value of generalized geometry by encompassing various structures (symplectic and complex structures are both generalized complex structures), reinterpreting involved ones (bihermitian geometry corresponds to generalized K\"ahler geometry), and introducing genuinely new structures (there are neither symplectic nor complex manifolds admitting generalized complex structures). Time permitting I will hint at some more recent directions of the theory.
Divendres 14 de juny, 15:10h, Aula T1, FMI-UB
Gian Pietro Pirola
Università di Pavia, Itàlia

Contact:
jcnaranjo at ub.edu
On the local geometry of the period map of curves The period map $$\tau:M_g\to A_g$$ gives an immersion (outside the hyperelliptic locus) of the moduli space of complex curves of genus $$g$$ into the moduli space of principally polarized abelian varieties of dimension $$g$$. We study the local geometry of this immersion by means of the natural riemannian (orbifold) structure induced on $$A_g$$ from Siegel space. In particular two methods to give a bound on the dimension of the totally geodesic subvarieties of $$A_g$$ contained in $$M_g$$ are discussed. The first one (Colombo-Frediani-Ghigi) uses the second fundamental form associated to the Torelli immersion and the second one (Ghigi-P-Torelli) uses instead a sort of local Fujita decomposition along geodesics. We recall that the Shimura varieties are (algebraic) totally geodesic subvarieties of $$A_g$$ and for $$g\gg 0$$, according to the Coleman-Oort conjecture, they should not be contained in $$\tau(M_g)$$.
Divendres 28 de juny, 15:10h, Aula T2, FMI-UB
 Cloenda del Seminari 2018-2019 Divendres 5 de juliolAula T1, FMI-UB Ciro Ciliberto Università di Roma Tor Vergata, Itàlia Nodal curves on Enriques surfaces In this talk I will consider Severi varieties of nodal curves in linear systems on Enriques surfaces. The problems I will treat are: the dimensionality problem of components of the Severi variety and the existence problem of such components on a general Enriques surface. 15:10h Cafè 16:10h Guillem Blanco Universitat Politècnica de Catalunya Yano's conjectureIn 1982, T. Yano proposed a conjecture about the generic $$b$$-exponents of an irreducible plane curve singularity. Given any holomorphic function $$f : (\mathbb{C}^2, \boldsymbol{0}) \longrightarrow (\mathbb{C}, 0)$$ defining an irreducible plane curve, the conjecture gives an explicit formula for the generic $$b$$-exponents of the singularity in terms of the characteristic sequence of $$f$$. In this talk, we will present a proof of Yano's conjecture. 16:40h Reunió - organització seminari 2019-2020 17:40h Rick Miranda Colorado State University, EUA Nonlinear Toric Degenerations We are motivated by considerations related to the Segre-Gimigliano-Harbourne-Hirschowitz conjecture, which deals with the dimension of linear systems of plane curves with prescribed multiple points. The plane is a toric surface, and several approaches to the SGHH problem involve toric constructions leading to auxiliary questions. One is: when does one toric surface degenerate to another? I’ll present several examples and a general technique which hopefully illustrate some of the subject’s general interest. Most of the talk should be accessible to non-experts. 18:15h Sopar 20:30

 Universitat de Barcelona Universitat Politècnica de Catalunya Universitat Autònoma de Barcelona


text:
## File: mathml.rst

package info (click to toggle)
mathjax-docs 2.7+20171212-1
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 .. _MathML-support: ********************** MathJax MathML Support ********************** The support for :term:MathML in MathJax comes in three parts: the mml2jax preprocessor, the MathML input processor, and the NativeMML output processor. The first of these looks for [itex] tags within your document and marks them for later processing by MathJax. The second converts the MathML to the internal format used by MathJax, and the third turns the internal format into MathML within the page so that it can be displayed by the browser's native MathML support. Because of MathJax's modular design, you do not need to use all three of these components. For example, you could use the tex2jax preprocessor and the TeX input processor, but the NativeMML output processor, so that your mathematics is entered in TeX format, but displayed as MathML. Or you could use the mml2jax preprocessor and MathML input processor with the HTML-CSS output processor to make MathML available in browsers that don't have native MathML support. It is also possible to have MathJax select the output processor for you so that MathML is used in those browsers that support it well enough, while HTML-CSS is used for those that don't. See the :ref:combined configurations  section for details and examples. Of course it is also possible to use all three components together. It may seem strange to go through an internal format just to return to MathML in the end, but this is actually what makes it possible to view MathML within an HTML4 page (rather than an XHTML page), in particular in older browsers, without the complications of handling special MIME-types for the document, or any of the other setup issues that make using native MathML difficult. MathJax handles the setup and properly marks the mathematics so that the browser will render it as MathML. In addition, MathJax provides its contextual menu for the MathML, which lets the user zoom the mathematics for easier reading, get and copy the source markup, and so on, so there is added value to using MathJax even with a pure MathML workflow. MathML in HTML pages ==================== For MathML that is handled via the preprocessor, you should not use named MathML entities, but rather use numeric entities like √ or unicode characters embedded in the page itself. The reason is that entities are replaced by the browser before MathJax runs, and some browsers report errors for unknown entities. For browsers that are not MathML-aware, that will cause errors to be displayed for the MathML entities. While that might not occur in the browser you are using to compose your pages, it can happen with other browsers, so you should avoid the named entities whenever possible. If you must use named entities, you may need to declare them in the DOCTYPE declaration by hand. When you use MathML in an HTML4 document rather than an XHTML one (MathJax will work with both), you should not use the "self-closing" form for tags with no content, but should use separate open and close tags. That is, use .. code-block:: html rather than . This is because HTML (prior to HTML5) does not have self-closing tags, and some browsers will get the nesting of tags wrong if you attempt to use them. For example, with , since there is no closing tag, the rest of the mathematics will become the content of the  tag; but since  should have no content, the rest of the mathematics will not be displayed. This is a common error that should be avoided. Modern browsers that support HTML5 should be able to handle self-closing tags, but older browsers have problems with them, so if you want your mathematics to be visible to the widest audience, do not use the self-closing form in HTML documents. Supported MathML commands ========================= MathJax supports the MathML3.0 _ mathematics tags, with some limitations. The MathML support is still under active development, so some tags are not yet implemented, and some features are not fully developed, but are coming. The deficiencies include: - No support for alignment groups in tables. - Not all attributes are supported for tables. E.g., columnspan and rowspan are not implemented yet. - Experimental support for the elementary math tags: mstack, mlongdiv, msgroup, msrow, mscarries, and mscarry. (Via the mml3 extension, see below.) - Experimental support for bidirectional mathematics. (Via the mml3 extension, see below.) See the results of the MathML3.0 test suite _ for details. .. _content-mathml: Content MathML ============== To use Content MathML in your documents, simply include "content-mathml.js" in the extensions array of your MathML configuration block. For example .. code-block:: html Note that this script tag must come *before* the script that loads MathJax.js itself. For more information, see :doc:options/extensions/Content-MathML. .. _experimental-mathml: Experimental mml3 extension =========================== To activate experimental features in your documents, simply include "mml3.js" in the extensions array of your MathML configuration block. For example .. code-block:: html Note that this script tag must come *before* the script that loads MathJax.js itself. For more information, see :doc:options/extensions/MML3. Semantics and Annotations ========================= Starting with MathJax version 2.3, some popular annotation formats like TeX, Maple, or Content MathML that are often included in the MathML source via the semantics element are accessible from the "Show Math As" menu. See the MathML Annotation Framework _ and the :ref:configure-MathMenu documentation for details.


text:
# Reverse Formula

#### Recable

##### New member
I'm sorry if this isn't in the right section on the forum but I don't actually know where to post this... but anyway - I need help with reversing this formula I made (through trial and error).

(1 / (points + 1)) + (0.1 / (points / 2))
When the points value is below 0, this is the formula I use to decrease the outcomes value. But it decreases by a smaller amount per point. So as an example:
-30
(1 / (1 + 1)) + (0.1 / (1 / 2)) = 0.70x [30% decreased value]
-27
(1 / (2 + 1)) + (0.1 / (2 / 2)) = 0.43x [57% decreased value]
-12
(1 / (3 + 1)) + (0.1 / (3 / 2)) = 0.31x [69% decreased value]
-6
(1 / (4 + 1)) + (0.1 / (4 / 2)) = 0.25x [75% decreased value]
-5
(1 / (5 + 1)) + (0.1 / (5 / 2)) = 0.20x [80% decreased value]

As you can see the next gap is always smaller than the last. Now the problem I'm having is making this reverse, so to make it so the value increases by 30%, 57%, etc.

P.S I know the points would be -1, -2, -3, etc - but I'll be calculating it so when the points are below 0 it uses this formula and then make the points an absolute value to make the above work. Also the values are rounded down to the nearest 2 decimal places.

Last edited:

#### Hope Spirit

##### New member
I don't think this is where this problem goes. I'm pretty sure arithmetic doesn't involve the things you need to solve this problem.

#### Recable

##### New member
I don't think this is where this problem goes. I'm pretty sure arithmetic doesn't involve the things you need to solve this problem.
Yeah I wasn't sure where to put it, I guess in the advanced bit?

#### JeffM

##### Elite Member
I'm sorry if this isn't in the right section on the forum but I don't actually know where to post this... but anyway - I need help with reversing this formula I made (through trial and error).

(1 / (points + 1)) + (0.1 / (points / 2))
When the points value is below 0, this is the formula I use to decrease the outcomes value. But it decreases by a smaller amount per point. So as an example:
-30
(1 / (1 + 1)) + (0.1 / (1 / 2)) = 0.70x [30% decreased value]
-27
(1 / (2 + 1)) + (0.1 / (2 / 2)) = 0.43x [57% decreased value]
-12
(1 / (3 + 1)) + (0.1 / (3 / 2)) = 0.31x [69% decreased value]
-6
(1 / (4 + 1)) + (0.1 / (4 / 2)) = 0.25x [75% decreased value]
-5
(1 / (5 + 1)) + (0.1 / (5 / 2)) = 0.20x [80% decreased value]

As you can see the next gap is always smaller than the last. Now the problem I'm having is making this reverse, so to make it so the value increases by 30%, 57%, etc.

P.S I know the points would be -1, -2, -3, etc - but I'll be calculating it so when the points are below 0 it uses this formula and then make the points an absolute value to make the above work. Also the values are rounded down to the nearest 2 decimal places.
Well this certainly does not belong in arithmetic, but we only ask that people give a good faith effort on that.

However, what you have asked is quite obscure. In your first example, you mention - 30. Is that the number of points? If so the number of points does not appear in your formula.

#### Recable

##### New member
Well this certainly does not belong in arithmetic, but we only ask that people give a good faith effort on that.

However, what you have asked is quite obscure. In your first example, you mention - 30. Is that the number of points? If so the number of points does not appear in your formula.
No that was the current decrease in value, -30, -27 etc as shown on the end of each new statement it says [-30%] etc. But the number of points are 1, 2, 3 etc just increasing by 1.

#### JeffM

##### Elite Member
If I am getting this, your current formula is

$$\displaystyle p \le -1 \implies y = \dfrac{1}{1 - p} + \dfrac{0.1}{\dfrac{-p}{2}} = \dfrac{- p + 0.2 - 0.2p}{(-p)(1 - p)} = - \dfrac{1.2p - 0.2}{p^2 - p}.$$

Let's see if that works.

p = -1, y = -(-1.2 - 0.2)/(1 + 1} = 0.7

p = -2, y = -(-2.4 - 0.2)/(4 + 2) = 2.6/6 = 0.43....

p = -3, y = -(-3.6 - 0.2)/(9 + 3) = 3.8/12 = 0.316

OK I have the computation. Now what do you mean by reversing it?

#### Recable

##### New member
If I am getting this, your current formula is

$$\displaystyle p \le -1 \implies y = \dfrac{1}{1 - p} + \dfrac{0.1}{\dfrac{-p}{2}} = \dfrac{- p + 0.2 - 0.2p}{(-p)(1 - p)} = - \dfrac{1.2p - 0.2}{p^2 - p}.$$

Let's see if that works.

p = -1, y = -(-1.2 - 0.2)/(1 + 1} = 0.7

p = -2, y = -(-2.4 - 0.2)/(4 + 2) = 2.6/6 = 0.43....

p = -3, y = -(-3.6 - 0.2)/(9 + 3) = 3.8/12 = 0.316

OK I have the computation. Now what do you mean by reversing it?
Okay I'm not quite sure what you did but yeah your results are the same as mine (0.7, 0.43, 0.31, etc). But by reverse I mean now I want to make my formula increase instead of decrease, so 1.30, 1.57, 1.69, etc. If that makes sense?

Edit: I mean I'm not sure what you did because I simply don't understand because I'm not that good at maths haha.

#### JeffM

##### Elite Member
Okay I'm not quite sure what you did but yeah your results are the same as mine (0.7, 0.43, 0.31, etc). But by reverse I mean now I want to make my formula increase instead of decrease, so 1.30, 1.57, 1.69, etc. If that makes sense?

Edit: I mean I'm not sure what you did because I simply don't understand because I'm not that good at maths haha.
Still with negative points or with positive points?

#### Recable

##### New member
Still with negative points or with positive points?
With positive points now.

#### JeffM

##### Elite Member
And do you want y to decrease as p increases (opposite to what happens with negative points)?

And what should happen with 0 points?

#### Cubist

##### Full Member
Also, are the exact values in the OP important? If not then a better, single, function that works over the whole domain of p may be possible. (What's the domain of p values?)

#### Recable

##### New member
And do you want y to decrease as p increases (opposite to what happens with negative points)?

And what should happen with 0 points?
Basically I wanted it so that when points are below 0, it reduces the main value by a certain amount. It decreases less each time per point though. The exact opposite of when points are above 0, so each point increases the main value but also increases it less per point. So 1.30x, 1.57x, etc. Instead of 0.7x, 0.43x etc. Does that make sense?

#### Recable

##### New member
Also, are the exact values in the OP important? If not then a better, single, function that works over the whole domain of p may be possible. (What's the domain of p values?)
What do you mean by the domain of p values?

#### JeffM

##### Elite Member
The domain of p means what values can p be allowed to take?

Must p be an integer? Can it be zero? Are there limits that it cannot surpass?

#### Cubist

##### Full Member

Here's the graph of a polynomial quotient that might fit the bill? in Desmos you can easily add sliders to "play around":- Desmos (click). By adding the derivative to the graph, you can be more sure that your curve always increases. The derivative ought to get closer the x axis from above as x increases, but it should never dip below.

You could also try looking at the graph of "ln(x)". When you're happy, then obviously substitute variable "p" for "x".

#### Cubist

##### Full Member
...or perhaps you simply want 2-f(-p) where f is your formula? Using JeffM's equation this would be...

$$\displaystyle 2 + \dfrac{-1.2p - 0.2}{p^2 + p}$$

$$\displaystyle =2 - \dfrac{1.2p + 0.2}{p^2 + p}$$

$$\displaystyle =\dfrac{2p^2+2p -(1.2p + 0.2)}{p^2 + p}$$

$$\displaystyle =\dfrac{2p^2+0.8p - 0.2 }{p^2 + p}$$

EDIT: giving 1.3, 1.566..., 1.6833... when p=1,2,3

#### Recable

##### New member
The domain of p means what values can p be allowed to take?

Must p be an integer? Can it be zero? Are there limits that it cannot surpass?
Oh right, yeah it's always a integer and it's never 0. It's only 1, 2, 3, etc and -1, -2, -3, etc.

Last edited:

#### Recable

##### New member
...or perhaps you simply want 2-f(-p) where f is your formula? Using JeffM's equation this would be...

$$\displaystyle 2 + \dfrac{-1.2p - 0.2}{p^2 + p}$$

$$\displaystyle =2 - \dfrac{1.2p + 0.2}{p^2 + p}$$

$$\displaystyle =\dfrac{2p^2+2p -(1.2p + 0.2)}{p^2 + p}$$

$$\displaystyle =\dfrac{2p^2+0.8p - 0.2 }{p^2 + p}$$

EDIT: giving 1.3, 1.566..., 1.6833... when p=1,2,3
Yeah that seems to be correct. Thanks, however after all this I feel really unsatisfied with myself in making the formula but also not fully understanding how to switch it around. Do you have any advice on where I can learn about it more?

#### Cubist

##### Full Member
Yeah that seems to be correct. Thanks, however after all this I feel really unsatisfied with myself in making the formula but also not fully understanding how to switch it around. Do you have any advice on where I can learn about it more?
Try not to feel negative, you'll learn much more if you can stay positive! We all have to start somewhere, don't be afraid of (re?) learning things that might seem basic. There are some resources on this site (click). And when the covid19 restrictions lift then maybe you could look into attending a night class.

#### Recable

##### New member
Try not to feel negative, you'll learn much more if you can stay positive! We all have to start somewhere, don't be afraid of (re?) learning things that might seem basic. There are some resources on this site (click). And when the covid19 restrictions lift then maybe you could look into attending a night class.
Thank you


text:
# Spatially Oversampled Demultiplexing in mmWave LoS MIMO

Abstract:

The transceiver separations required for synthesizing full rank MIMO matrices in line of sight (LoS) geometries scale as the square root of the product of carrier wavelength
and range. The wavelengths at millimeter (mm) wave carrier frequencies are small therefore enable LoS spatial multiplexing with practical node form factors at ranges of 10-100 m, depending on the carrier frequency. However, such LoS MIMO links become frequency selective even with small geometric mismatches. Exact channel inversion in an
$N \times N$ MIMO system requires fractionally spaced equalization, which is practically infeasible when operating at the very high data rates (multiple Gbps) that we are interested in. In this paper, we investigate spatial oversampling (more receive antennas than transmitted data streams) with symbol rate sampling, introducing {\it designed} delay diversity across different receive antennas, as a means for removing error floors when linearly separating the spatially multiplexed streams. We study the tradeoff between the number of additional receive antennas and the complexity of temporal equalization, and argue that an attractive example architecture, compatible with form factor constraints, is one in which the number of receive antennas is double the number of transmitted data streams.

### Paper Details

Authors:
Submitted On:
23 June 2018 - 1:57pm
Type:
Poster
Event:
Presenter's Name:
Raviteja Patchava
Document Year:
2018

### Subscribe

[1] P. Raviteja, U. Madhow, "Spatially Oversampled Demultiplexing in mmWave LoS MIMO", IEEE SigPort, 2018. [Online]. Available: http://sigport.org/3315. Accessed: Nov. 16, 2018.
@article{3315-18,
url = {http://sigport.org/3315},
author = {P. Raviteja; U. Madhow },
publisher = {IEEE SigPort},
title = {Spatially Oversampled Demultiplexing in mmWave LoS MIMO},
year = {2018} }
TY - EJOUR
T1 - Spatially Oversampled Demultiplexing in mmWave LoS MIMO
AU - P. Raviteja; U. Madhow
PY - 2018
PB - IEEE SigPort
UR - http://sigport.org/3315
ER -
P. Raviteja, U. Madhow. (2018). Spatially Oversampled Demultiplexing in mmWave LoS MIMO. IEEE SigPort. http://sigport.org/3315
P. Raviteja, U. Madhow, 2018. Spatially Oversampled Demultiplexing in mmWave LoS MIMO. Available at: http://sigport.org/3315.
P. Raviteja, U. Madhow. (2018). "Spatially Oversampled Demultiplexing in mmWave LoS MIMO." Web.
1. P. Raviteja, U. Madhow. Spatially Oversampled Demultiplexing in mmWave LoS MIMO [Internet]. IEEE SigPort; 2018. Available from : http://sigport.org/3315


text:
NIPS 2017
Mon Dec 4th through Sat the 9th, 2017 at Long Beach Convention Center
Paper ID: 2035 A multi-agent reinforcement learning model of common-pool resource appropriation

### Reviewer 1

An interesting take on modelling the CPR dilemma. From a social science perspective and purely as future work, it would be interesting to see the following: 1. How the agents behave if they are aware of the type of opponents in their local view (zapper/non-zapper). Does it lead them to form a (temporary?) alliance or do they tend to avoid each other. 2. The effects of varying the rate at which resources are harvested for a part of the agent population.

### Reviewer 2

* Summary Authors introduce a novel multi-agent problem (from machine learning's perspective) of common-pool resource appropriation and study how independently learning agents, while trying to optimize certain incentives, can learn to avoid "tragedy of the commons". The authors find that in certain environments, the learned strategies are consistent with predictions from economics. * Strengths The paper is well written and argued paper introducing a novel problem applying techniques of multi-agent reinforcement learning to model possible mechanisms by which intelligent agents can learn to avoid "tragedy of the commons". It shows how modern machine learning methods, when applied appropriately can add more fidelity to the model under study, while still maintaining some tractability. The authors clearly mention the limitations of the model and avoid making any comments about the social-economical implications. * Weaknesses - The paper is not self contained Understandable given the NIPS format, but the supplementary is necessary to understand large parts of the main paper and allow reproducibility. I also hereby request the authors to release the source code of their experiments to allow reproduction of their results. - Use of deep-reinforcement learning is not well motivated The problem domain seems simple enough that a linear approximation would have likely sufficed? The network is fairly small and isn't "deep" either. - > We argue that such a mechanism is more realistic because it has an effect within the game itself, not just on the scores This is probably the most unclear part. It's not clear to me why the paper considers one to be more realistic than the other rather than just modeling different incentives? Probably not enough space in the paper but actual comparison of learning dynamics when the opportunity costs are modeled as penalties instead. As economists say: incentives matter. However, if the intention was to explicitly avoid such explicit incentives, as they _would_ affect the model-free reinforcement learning algorithm, then those reasons should be clearly stated. - Unclear whether bringing connections to human cognition makes sense As the authors themselves state that the problem is fairly reductionist and does not allow for mechanisms like bargaining and negotiation that humans use, it's unclear what the authors mean by Perhaps the interaction between cognitively basic adaptation mechanisms and the structure of the CPR itself has more of an effect on whether self-organization will fail or succeed than previously appreciated.'' It would be fairly surprising if any behavioral economist trying to study this problem would ignore either of these things and needs more citation for comparison against "previously appreciated". * Minor comments ** Line 16: > [18] found them... Consider using \citeauthor{} ? ** Line 167: > be the N -th agent’s should be i-th agent? ** Figure 3: Clarify what the fillcolor implies and how many runs were the results averaged over? ** Figure 4: Is not self contained and refers to Fig. 6 which is in the supplementary. The figure is understandably large and hard to fit in the main paper, but at least consider clarifying that it's in the supplementary (as you have clarified for other figures from the supplementary mentioned in the main paper). ** Figure 5: - Consider increasing the axes margins? Markers at 0 and 12 are cut off. - Increase space between the main caption and sub-caption. ** Line 299: From Fig 5b, it's not clear that |R|=7 is the maximum. To my eyes, 6 seems higher.