Geodesic
An asymptotically sharp bound on the maximum number of independent transversals
Jake Ruotolo1 ; Kevin Wang2 ; Fan Wei3
1Harvard University
2University of Iowa
3Princeton University
The electronic journal of combinatorics, Tome 31 (2024) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be a multipartite graph with partition $V_1, V_2,\ldots, V_k$ of $V(G)$. Let $d_{i,j}$ denote the edge density of the pair $(V_i, V_j)$. An independent transversal is an independent set of $G$ with exactly one vertex in each $V_i$. In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the $d_{i,j}$'s.
DOI : 10.37236/11670
Classification : 05C30, 05D15, 05C35, 05C69, 05C70
Mots-clés : odd cycle decomposition of a graph, geometric mean

Jake Ruotolo  1   ; Kevin Wang  2   ; Fan Wei  3

1 Harvard University
2 University of Iowa
3 Princeton University 
@article{10_37236_11670,
     author = {Jake Ruotolo and Kevin Wang and Fan Wei},
     title = {An asymptotically sharp bound on the maximum number of independent transversals},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {1},
     doi = {10.37236/11670},
     zbl = {1536.05253},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11670/}
}
TY  - JOUR
AU  - Jake Ruotolo
AU  - Kevin Wang
AU  - Fan Wei
TI  - An asymptotically sharp bound on the maximum number of independent transversals
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11670/
DO  - 10.37236/11670
ID  - 10_37236_11670
ER  - 
%0 Journal Article
%A Jake Ruotolo
%A Kevin Wang
%A Fan Wei
%T An asymptotically sharp bound on the maximum number of independent transversals
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11670/
%R 10.37236/11670
%F 10_37236_11670
Jake Ruotolo; Kevin Wang; Fan Wei. An asymptotically sharp bound on the maximum number of independent transversals. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11670

Cité par Sources :