Questions tagged [extremal-graph-theory]

Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.

Filter by
Sorted by
Tagged with
1 vote
0 answers
65 views

Partitioning of a set family that avoids small intersections

Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
user avatar
6 votes
0 answers
76 views

Maximum number of cycles on regular graphs

Let $G$ be a $d$-regular graph on $n$ vertices. I'm interested in upper bounds on the number of cycles of length $k$ that hold for any such $G$. The regime I'm interested in is: $d$ is fixed, and $...
user avatar
7 votes
0 answers
119 views

Inequality of product of discrete cosines

Let $k,a,b,c$ be odd positive integers. Consider the following inequality: $$ \sum_{x,y \in [k]} \cos^a\bigg(\frac{2\pi}{k}\cdot x\bigg) \cdot \cos^b\bigg(\frac{2\pi}{k}\cdot y\bigg) \cdot \cos^c\bigg(...
user avatar
1 vote
2 answers
218 views

Graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices. Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{...
user avatar
4 votes
1 answer
103 views

Explicit constructions of regular graphs with very sparse induced subgraphs

Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
user avatar
1 vote
0 answers
20 views

Topology of densest graphs whose optimal $3D$-matching can be calculated efficiently

let $A=\lbrace a_1,\,\dots,\,a_k\rbrace $ and $B=\lbrace b_1,\,\dots,\,b_{2k}\rbrace,\ A\cap B=\emptyset$ be be a partition of a graph's vertex set $V$, i.e. $V\,=\,A\cup B$. Question: has $G:=\...
user avatar
1 vote
1 answer
86 views

Connected sets with a large boundary in a privileged set

Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e. $$\partial S = \{v\not \in S: \...
user avatar
  • 16.7k
4 votes
0 answers
90 views

Connected sets with large boundary in a multigraph

Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e. $$\partial S = \{v\not \in S: \...
user avatar
  • 16.7k
2 votes
1 answer
110 views

3-uniform tetrahedron-free hypergraph on seven vertices

My problem concerns 3-uniform hypergraphs. Let $f(n)$ be the maximal number of edges in a 3-uniform hypergraph such that no four edges form a "tetrahedron", i.e., four edges that join the ...
user avatar
  • 2,265
3 votes
0 answers
133 views

Graphs with high girth and low diameter

As the title says, I'm interested in graphs with high girth and low diameter. Given a class $\Gamma$ of finite $k$-regular graphs, call a $\Gamma$-graph GD-extremal if every $\Gamma$-graph either has ...
user avatar
1 vote
0 answers
14 views

Is homomorphism density of partially labeled graph continuous with respect to cut metric

Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
user avatar
5 votes
1 answer
147 views

Graph combinatorial optimization problem

Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. ...
user avatar
1 vote
1 answer
123 views

Combinatorial graph optimization problem on integer adjacency matrices

We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers. Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and $z:=\...
user avatar
2 votes
1 answer
81 views

The lower bound of number of vertices covered by maximum matching in $3$-regular graph

Let $G$ be a $3$-regular graph (cubic graph) with order $n$. From here, the lower bound of # of vertices covered by maximum matching in $G$ is $\frac{3}{4}n$. And from here, the lower bound is $\frac{...
user avatar
  • 321
3 votes
2 answers
218 views

Ramsey-Turán density function is well defined

Define $$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$ and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as $$f_l(\alpha)=\lim_{n\to \infty}...
user avatar
0 votes
1 answer
92 views

A general Turan-like question

Thinking of an edge as of a $2$-clique, it's natural to consider a slightly more general question than Turan considered in his celebrated theorem: given $r \le k \le n$, what is the maximal possible ...
user avatar
2 votes
0 answers
50 views

Two conjectures on a special type of graph

I want to analyze a special type of weighted directed graph where out degrees is equal to in degrees at each vertex. $n \in Z$ and $n \geq 3$ , Set $x_n=\left(1,1,\dots,1\right)^T \in \mathbb{R}^{n}...
user avatar
0 votes
0 answers
17 views

Does a connected $F_k$-free graph of order $n$ with the maximum singless Laplacian spectral radius belong to $Ex(n,F_k)$?

Let $G$ be a connected $F_k$-free graph of order $n$ with the maximum singless Laplacian spectral radius. Is $G\in Ex(n,F_k)$? Here, $Ex(n,H)$ denotes the set of $H$-free graphs of order $n$ with $ex(...
user avatar
  • 780
2 votes
0 answers
53 views

Beurling’s extremality criterion for curves: two versions

I see Beurling’s extremality criterion at two places: the proof is almost identical, but the statement is very different. Below, $$ \ell_\rho (\gamma) = \int_\gamma \rho(z) |dz|. $$ "Extremal&...
user avatar
  • 1,457
1 vote
1 answer
50 views

Graph with two edge-disjoint Hamiltonian paths between the same vertex-pair

Provided existence, what is the smallest graph $G(V,E)$ with two edge-disjoint Hamiltonian paths between $u$ and $v;\ \lbrace u,v\rbrace\subset V$?
user avatar
3 votes
1 answer
68 views

Turán density of an unbalanced complete $r$-partite $r$-graph

In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following: Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
user avatar
4 votes
2 answers
562 views

The number of monochromatic triangles

It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula $$M(n)=\binom n3-\left\lfloor\frac n2\...
user avatar
  • 8,573
10 votes
2 answers
396 views

Conjecture on minimum size of graph

Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
user avatar
  • 215
4 votes
3 answers
343 views

How to show that random graphs cannot be embedded with short edges

For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio $$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
user avatar
0 votes
0 answers
65 views

(Weakly) connected sets with large (out-)boundary

Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
user avatar
  • 16.7k
2 votes
1 answer
125 views

Combinatorial process on multisets of integers

Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments: We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
user avatar
2 votes
0 answers
107 views

What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph

By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
user avatar
  • 982
2 votes
0 answers
36 views

Expectation of Hadwiger number of a random graph

For any integer $n$, let ${\cal G}_n$ denote the set of simple, undirected graphs $G = (V, E)$ where $V = \{1,\ldots,n\}$. The Hadwiger number $\eta(G)$ of a finite graph $G$ is the maximum integer $m$...
user avatar
1 vote
0 answers
70 views

Expected value of the difference of the Hadwiger number and the chromatic number

If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of ...
user avatar
6 votes
2 answers
345 views

Snake algorithm that minimizes straight lines

How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself? Here's an example we have ...
user avatar
  • 61
3 votes
1 answer
82 views

Minimum size of regular graph with no short cycles

For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
user avatar
13 votes
2 answers
531 views

Graph in which no cycle has two crossing chords

Let $G$ be a graph which does not contain a simple cycle $v_1\ldots v_k$ and two "crossing" chords $v_iv_j$ and $v_pv_q$, $i<p<j<q$. An example of such graph is a triangulation of ...
user avatar
  • 86.9k
1 vote
0 answers
83 views

Number of maximum matchings in bipartite graphs of positive surplus

Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...
user avatar
17 votes
3 answers
424 views

Graph that minimizes the number of b/w colorings where white vertices have an odd number of black

motivated from a physical context, we are currently interested in the following graph coloring problem: Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
user avatar
  • 313
2 votes
1 answer
85 views

Smallest size of graph covered by infinite tree

Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
user avatar
0 votes
1 answer
77 views

Making graphs isomorphic with edge additions/removals

Consider simple graphs on the same vertex set $[n]$. For two graphs $G, H$, let $d(G, H) = \min_{H' \sim H} |E(G) \triangle E(H')|$ — the smallest number of edge additions/removals needed to make $G$ ...
user avatar
16 votes
1 answer
536 views

Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991), if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
user avatar
  • 16.7k
7 votes
0 answers
153 views

Szemerédi's regularity lemma for binary operations

Szemerédi's regularity lemma is an approximate structure theorem for all large graphs (symmetric binary relations). There are versions for multicolored graphs and directed graphs. Is there an ...
user avatar
10 votes
0 answers
121 views

Largest number of simple paths between two vertices

Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$. A recent IOI problem utilized ...
user avatar
3 votes
1 answer
119 views

Independence number of $C_4$-free graphs

It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$. This bound cannot be improved over $\Theta(n^{\...
user avatar
  • 7,982
3 votes
0 answers
75 views

Connected set of vertices having large boundary in a subset?

Let $\Gamma = (V,E)$ be a connected (undirected) graph where every vertex has degree $\geq 2$. Let $E'\supset E$ be a larger set of edges between elements of $V$ such that every vertex of $\Gamma'=(V,...
user avatar
  • 16.7k
3 votes
0 answers
67 views

Boundary differences in two graphs

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
user avatar
  • 16.7k
2 votes
0 answers
96 views

Existence of a subcover with large boundary

Let $\mathscr{C}$ be a cover of $\mathbf{N}=\{1,2,\dotsc,N\}$ by finite subsets $S\in \mathscr{C}$ with $2\leq |S|\leq K$, where we write $|S|$ for the number of elements of $S$. Assume no element of $...
user avatar
  • 16.7k
2 votes
1 answer
215 views

Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
user avatar
  • 725
4 votes
0 answers
93 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
user avatar
0 votes
1 answer
49 views

Matching book thickness of the wheel graph $W_n$

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
user avatar
3 votes
2 answers
292 views

Existence of connected component with large boundary?

Question 1. Let $\Gamma=(V,E)$ be a connected graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, ...
user avatar
  • 16.7k
1 vote
0 answers
57 views

4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ...
user avatar
  • 1,054
9 votes
2 answers
384 views

Graph metric approximating Euclidean metric

I've been reading Wolfram's recent articles about graph/mesh/grid structures as an analogy for physical space, and it seems to me that there will be a problem getting the notion of distance to work ...
user avatar
4 votes
0 answers
73 views

Expected number of bridges in a random subgraph

I am researching connectivity in random subgraphs and have come across the following problem. A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
user avatar
  • 175