Rémi de Joannis de Verclos
Laboratoire G-SCOP, bureau B521
46 avenue Félix Viallet
38031 Grenoble Cedex 1
France
Tel: +33 (0) 4 56 52 98 22
E-mail: remi.de-joannis-de-verclos@grenoble-inp.fr
I am a PhD student under the direction of Louis Esperet and Jean-Sébastien Sereni.
We demonstrate that for every positive integer $\Delta$, every $K_4$-minor-free graph with maximum degree $\Delta$ admits an equitable coloring with $k$ colors where $k \ge (\Delta+3)/2$. This bound is tight and confirms a conjecture by Zhang and Whu. We do not use the discharging method but rather exploit decomposition trees of $K_4$-minor-free graphs.
It was conjectured by Jaeger, Linial, Payan, and Tarsi in 1992 that for any prime number $p$, there is a constant $c$ such that for any $n$, the union (with repetition) of the vectors of any family of $c$ linear bases of $\mathbb{Z}_p^n$ forms an additive basis of $\mathbb{Z}_p^n$ (i.e. any element of $\mathbb{Z}_p^n$ can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two non-zero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that $p\ge 3$ is a prime number and $\vec{G}$ is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in $\mathbb{Z}_p$. Then $\vec{G}$ has a $\mathbb{Z}_p$-flow in which each arc is assigned a value of its own list.
Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in $MA$ having no arithmetic circuits of size $O(n^k)$ over the complex field (allowing any complex constant). We also build a family of polynomials that can be evaluated in AM having no arithmetic circuits of size $O(n^k)$. Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that $NP \not\subset size(n^k)$, or $MA \subset size(n^k)$, or $NP=MA$ imply lower bounds on the circuit size of uniform polynomials in n variables from the class $VNP$ over the complex field, assuming GRH. In positive characteristic p, uniform polynomials in VNP have circuits of fixed-polynomial size if and only if both $VP=VNP$ over $\mathbb{F}_p$ and $Mod_pP$ has circuits of fixed-polynomial size.
This paper considers the quasi-random rumor spreading model introduced by Doerr, Friedrich, and Sauerwald, hereafter referred to as the \em{list-based model}. Each node is provided with a cyclic list of all its neighbors, and, upon reception of a message, it chooses a random position in its list, and from then on calls its neighbors in the order of the list. This model is known to perform asymptotically at least as well as the random phone-call model, for many network classes. Motivated by potential applications of the list-based model to live streaming, we are interested in its worst case behavior.
Our first main result is the design of an $O(m+n\log n)$-time algorithm that, given any n-node m-edge network G, and any source-target pair $s,t\in V(G)$, computes the maximum number of rounds it may take for a rumor to be broadcast from $s$ to $t$ in $G$, in the list-based model. Hence, the list-based model is computationally easy to tackle in its basic version. The situation is radically different when one is considering variants of the model in which nodes are aware of the status of their neighbors, i.e., are aware of whether or not they have already received the rumor, at any point in time. Indeed, our second main result states that, unless P=NP, the worst case behavior of the list-based model with the additional feature that every node is perpetually aware of which of its neighbors have already received the rumor cannot be approximated in polynomial time within a $(\frac{1}{n})^{\frac{1}{2}-\epsilon}$ multiplicative factor, for any $\epsilon>0$. As a byproduct of this latter result, we can show that, unless $P=NP$, there are no PTAS enabling to approximate the worst case behavior of the list-based model, whenever every node perpetually keeps track of the subset of its neighbors which have sent the rumor to it so far.