BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jean-Sébastien Sereni

Jean-Sébastien Sereni appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsData Structures and AlgorithmsComputer Science and Game TheoryDistributed, Parallel, and Cluster Computingmath-phmath.MP

Catalog footprint

What is connected

18works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2020arXiv

An algorithmic framework for colouring locally sparse graphs

We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $Δ$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le Δ^\frac{2\varepsilon}{1+2\varepsilon}/(\logΔ)^2$, with $\lfloor(1+\varepsilon)Δ/\log(Δ/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bipartite independence number in graphs with bounded maximum degree

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t, t}$ in the bipartite complement of $G$. Let $f(n, Δ)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $Δ$ in one of the parts has a bi-hole of size $k$. Determining $f(n, Δ)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. Our main result determines the asymptotic behavior of $f(n, Δ)$. More precisely, we show that for large but fixed $Δ$ and $n$ sufficiently large, $f(n, Δ) = Θ(\frac{\log Δ}Δ n)$. We further address more specific regimes of $Δ$, especially when $Δ$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$, though determining the precise value of $f(n, 3)$ is still open.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph structure via local occupancy

The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lovász local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the effect of symmetry requirement for rendezvous on the complete graph

We consider a classic rendezvous game where two players try to meet each other on a set of $n$ locations. In each round, every player visits one of the locations and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of $\frac{n+1}{2}$ is achieved by the wait-for-mommy pair of strategies, where one of the players stays at one location for $n$ rounds, while the other player searches through all the $n$ locations in a random order. However, if we insist that the players are symmetric --- they are expected to follow the same strategy --- then the best known strategy, proposed by Anderson and Weber, achieves an asymptotic expected waiting time of $0.829 n$. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every $n\geqslant 2$, if the players need to employ the same strategy, then the expected waiting time is at least $\frac{n+1}{2}+\varepsilon n$, where $\varepsilon=2^{-36}$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Variations on the Petersen colouring conjecture

The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with $5$ colours such that for every edge $e$, the set of colours assigned to the edges adjacent to $e$ has cardinality either $2$ or $4$, but not $3$. We prove that every bridgeless cubic graph $G$ admits an edge-colouring with $4$ colours such that at most $\frac45\cdot|V(G)|$ edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a $4$-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Closeness Centralization Measure for Two-mode Data of Prescribed Sizes

We confirm a conjecture by Everett, Sinclair, and Dankelmann~[Some Centrality results new and old, J. Math. Sociology 28 (2004), 215--227] regarding the problem of maximizing closeness centralization in two-mode data, where the number of data of each type is fixed. Intuitively, our result states that among all networks obtainable via two-mode data, the largest closeness is achieved by simply locally maximizing the closeness of a node. Mathematically, our study concerns bipartite graphs with fixed size bipartitions, and we show that the extremal configuration is a rooted tree of depth~$2$, where neighbors of the root have an equal or almost equal number of children.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Equitable coloring of sparse planar graphs

A proper vertex coloring of a graph $G$ is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $χ_{eq}^*(G)$ of $G$ is the smallest integer $m$ such that $G$ is equitably $n$-colorable for all $n\ge m$. We show that for planar graphs $G$ with minimum degree at least two, $χ_{eq}^*(G)\le 4$ if the girth of $G$ is at least $10$, and $χ_{eq}^*(G)\le 3$ if the girth of $G$ is at least $14$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Toward more localized local algorithms: removing assumptions concerning global knowledge

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and $(Δ+1)$-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the $O(Δ2)$-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree $Δ$ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Two floor building needing eight colors

Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of $3$-dimensional parallelepiped arrangements. In the case each parallelepiped is within one floor, a direct application of the Four-Colour Theorem yields that the adjacency graph has chromatic number at most $8$. We provide an example of such an arrangement needing exactly $8$ colours. We also discuss bounds on the chromatic number of the adjacency graph of general arrangements of $3$-dimensional parallelepipeds according to geometrical measures of the parallelepipeds (side length, total surface or volume).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Transversals of Longest Paths and Cycles

Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) \leq ceiling(n/4-n^{2/3}/90), if G is connected, lct(G) \leq ceiling(n/3-n^{2/3}/36), if G is 2-connected, and \lpt(G) \leq 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister \emph{et al.} the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Multiple Petersen subdivisions in permutation graphs

A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if e is an edge of M such that every 4-cycle containing an edge of M contains e, then e is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of M is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Every plane graph of maximum degree 8 has an edge-face 9-colouring

An edge-face colouring of a plane graph with edge set $E$ and face set $F$ is a colouring of the elements of $E \cup F$ such that adjacent or incident elements receive different colours. Borodin proved that every plane graph of maximum degree $Δ\ge10$ can be edge-face coloured with $Δ+1$ colours. Borodin's bound was recently extended to the case where $Δ=9$. In this paper, we extend it to the case $Δ=8$.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

3-facial colouring of plane graphs

A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture.

0 citations0 reviewsNo code linkedOpen access