Concept
Coloration fractionnaire
Publications associées (52)
The Power of Two Matrices in Spectral Algorithms for Community Recovery
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...
Ieee-Inst Electrical Electronics Engineers Inc2024Unambiguous DNFs and Alon-Saks-Seymour
Mika Tapani Göös, Siddhartha Jain
We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...
IEEE COMPUTER SOC2022Edge colorings of graphs without monochromatic stars
In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...
ELSEVIER2020