Hypergraphs of Low Degree Without Independent Transversals
En palabras de los autores
For every fixed and every integer , we construct a finite vertex-partitioned -uniform hypergraph with blocks of size and no independent transversal. We show that the maximum number of edges meeting a block is while the maximum vertex degree is . This shows that the known bound on the number of edges meeting a block is asymptotically sharp even when the leading constant in the maximum vertex degree tends to zero, which answers a problem of Groenland, Kaiser, Treffers, and Wales. By blowing up the same construction, we further obtain for arbitrarily large , there exists a -uniform hypergraph with blocks, each of size at least , and , but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 8 pages,1 figure