Graph powers

MaRDI QIDQ4550231zbMATH OpenFDO

Authors Noga Alon

Publication date 20 January 2003

zbMATH Keywords

Shannon capacitySperner capacity

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

Certain questions in areas such as information theory, communication complexity, geometry, and Ramsey theory gives rise to problems involving the asymptotic behaviour of certain parameters of powers of a fixed graph. The author discusses results, conjectures, open questions, and proof techniques for a number of problems of this type. For the entire collection see [Zbl 0988.00023].

Recommendations

• Independence ratios of graph powers
• Problem 83
• scientific article; zbMATH DE number 723367
• Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon
• Problems and results in combinatorial analysis and graph theory

Cited in

(13)

• Asymptotic values of the Hall-ratio for graph powers
• Local chromatic number and Sperner capacity
• Shannon capacity and the categorical product
• The inner power of a graph
• Hamilton cycles in strong products of graphs
• A limit theorem for the Shannon capacities of odd cycles. II
• On minrank and forbidden subgraphs
• On the normalized Shannon capacity of a union
• Colouring strong products
• Essentially tight bounds for rainbow cycles in proper edge-colourings
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• On the ratio of Shannon numbers of graphs
• Cartesian powers of graphs can be distinguished by two labels

This page was built for publication: Graph powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4550231)