pipette
ENEnglish

Hypergraphs of Low Degree Without Independent Transversals

Xinzhe Song, Xia Wang

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 8 pages,1 figure