Skip to main content
added 20 characters in body
Source Link
Johnny Cage
  • 1.6k
  • 2
  • 12
  • 18

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed number of vertices without $K_{l,r}$ as a subgraph. A main example of this is $l=r=2$ (namely, cycles of length 4), due to its connection, for instance, with Sidon sets.

My question is the following: what is it known for a similar problem, but when avoiding an 'small' bipartite subgraph, not necessarily a complete $K_{l,r}$?

More precisely, I have in mind the following problem: consider $2n$ vertices, with partition of $n$ and $n$ vertices. Which is the maximum number of edges we can take in the corresponding bipartite graph without creating a $P_4$ (path with 4 edges)? Roughly speaking, the $C_4$ case is a degenerated situation of this.

Knowing references about other small configurations NOT coming from a complete $K_{l,r}$ would be also great appreciated.

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed number of vertices without $K_{l,r}$ as a subgraph. A main example of this is $l=r=2$ (namely, cycles of length 4), due to its connection, for instance, with Sidon sets.

My question is the following: what is it known for a similar problem, but when avoiding an 'small' bipartite subgraph, not necessarily a complete $K_{l,r}$?

More precisely, I have in mind the following problem: consider $2n$ vertices, with partition of $n$ and $n$ vertices. Which is the maximum number of edges we can take in the corresponding bipartite graph without creating a $P_4$? Roughly speaking, the $C_4$ case is a degenerated situation of this.

Knowing references about other small configurations NOT coming from a complete $K_{l,r}$ would be also great appreciated.

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed number of vertices without $K_{l,r}$ as a subgraph. A main example of this is $l=r=2$ (namely, cycles of length 4), due to its connection, for instance, with Sidon sets.

My question is the following: what is it known for a similar problem, but when avoiding an 'small' bipartite subgraph, not necessarily a complete $K_{l,r}$?

More precisely, I have in mind the following problem: consider $2n$ vertices, with partition of $n$ and $n$ vertices. Which is the maximum number of edges we can take in the corresponding bipartite graph without creating a $P_4$ (path with 4 edges)? Roughly speaking, the $C_4$ case is a degenerated situation of this.

Knowing references about other small configurations NOT coming from a complete $K_{l,r}$ would be also great appreciated.

Source Link
Johnny Cage
  • 1.6k
  • 2
  • 12
  • 18

Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed number of vertices without $K_{l,r}$ as a subgraph. A main example of this is $l=r=2$ (namely, cycles of length 4), due to its connection, for instance, with Sidon sets.

My question is the following: what is it known for a similar problem, but when avoiding an 'small' bipartite subgraph, not necessarily a complete $K_{l,r}$?

More precisely, I have in mind the following problem: consider $2n$ vertices, with partition of $n$ and $n$ vertices. Which is the maximum number of edges we can take in the corresponding bipartite graph without creating a $P_4$? Roughly speaking, the $C_4$ case is a degenerated situation of this.

Knowing references about other small configurations NOT coming from a complete $K_{l,r}$ would be also great appreciated.