Publication

Extremal number of graphs from geometric shapes

2025

Abstract

We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. The prism C2ℓ◻:=C2ℓ◻K2 is the graph consisting of two vertex disjoint 2ℓ-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every ℓ ≥ 4, ex(n,C2ℓ◻)=Θ(n3/2). This resolves a conjecture of He, Li and Feng. The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles. We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Bradač, Janzer, Sudakov and Tomon. Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice. (Figure presented.)

Official source

https://infoscience.epfl.ch/entities/publication/cdc40a4f-b1c6-408d-9b34-dc0662ed5e72

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2025

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/cdc40a4f-b1c6-408d-9b34-dc0662ed5e72

About this result

Related concepts (32)

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Extremal graph theory

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.

Related publications (21)

Extremal number of graphs from geometric shapes

Chat with Graph Search

Spectral Clustering with Side Information

Learning on Graphs with Long-Range Dependencies: Methods and Applications

A Framework for Efficient Estimation of Closeness Centrality and Eccentricity in Large Networks