Skip to main content

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
0 votes
0 answers
16 views

Homomorphism density of complete bipartite graph via local Sidorenko

Let $0<p<1$ and $G$ be a graphon with edge density $p$ and $\lVert G-p \rVert_\square\leq1.1p.$ Let $K_{ab}$ be a complete bipartite graph with each part's order $a,b.$ Let $t(K_{ab},G)$ be the ...
bc a's user avatar
  • 155
0 votes
0 answers
48 views

Cut norm via power trick

Let $G$ be a graph with vertex set $V$ and edge set $E(G)$, define it's $k$'th power trick as a graph $G^k$ with vertex set $V^k$ and for any $x=(x_1,x_2,\dots , x_k), y=(y_1,y_2,\dots , y_k)\in V^k$, ...
bc a's user avatar
  • 155
0 votes
0 answers
40 views

Does "epsilon-regular" equal to "cut distance less than epsilon"?

Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal? $G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
bc a's user avatar
  • 155
0 votes
0 answers
34 views

Property of edge-vertex transitive graphs

Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
bc a's user avatar
  • 155
3 votes
1 answer
139 views

Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?

Does the following holds? For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$, $$t(H,G)\geq t(K_2, G)^{e(H)}.$$ If not sure, is this a equal question as ...
bc a's user avatar
  • 155
0 votes
0 answers
27 views

Does there exist a Graph Counting Lemma in the Cut density condition?

Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...
bc a's user avatar
  • 155
0 votes
0 answers
36 views

Does this "linear-approximated" version of Graph Counting Lemma hold?

Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
bc a's user avatar
  • 155
4 votes
1 answer
318 views

A question related to "Locally Sidorenko" type problem

Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant. Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
bc a's user avatar
  • 155
3 votes
1 answer
68 views

Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
Siddhu Neehal's user avatar
4 votes
1 answer
182 views

Sizes of triangle-free graphs with independence number $k$

A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of ...
L.C. Zhang's user avatar
  • 1,749
4 votes
0 answers
135 views

"Neighborhood-Bounded" regular graphs

Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...
Mary_Smith's user avatar
0 votes
0 answers
89 views

Turán number of even cycles with diagonal

Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle. What is known about the Turán ...
domotorp's user avatar
  • 18.5k
2 votes
0 answers
56 views

Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi: Lemma: For any $\alpha>0$ and a graph $F$, ...
Isomorphism's user avatar
1 vote
1 answer
69 views

Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$. Let $C(V_i)$ be the union of ...
Fabius Wiesner's user avatar
1 vote
2 answers
69 views

The edit distance from a large complete $p$-partite graph to the Turán graph

Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turán graph. Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
Zeta's user avatar
  • 13
0 votes
0 answers
25 views

From average degree to a highly connected subhypergraph

I'm looking for a result in $k$-uniform hypergraphs analogous to the following result for graphs, due to Mader: Every graph of average degree $4r$ has a $r$-connected subgraph.
kleinbottle's user avatar
4 votes
1 answer
127 views

Longest paths and cycles in Steiner triple systems

A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists of $2t$ cyclically ...
X. Li's user avatar
  • 373
1 vote
1 answer
155 views

Gentle(-er) Introduction to Erdős–Bollobás's solution to Ramsey–Turán Type Problem

I am currently trying to understand the construction of maximal graph which contains no $K_4$ and sub-linear number of independent points in the graph. The original paper On a Ramsey–Turán type ...
total dependent random choice's user avatar
4 votes
0 answers
100 views

What properties do graphs avoiding large regular subgraphs have?

Fix a positive integer $r$ and real $\delta \in (0,1)$. Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
Naysh's user avatar
  • 507
3 votes
1 answer
131 views

Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
Lorenzo Pompili's user avatar
2 votes
0 answers
46 views

Size of set of positive integers no sum of two distinct elements giving square

Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square. Consider a graph with $n$ vertices: $x$ and ...
Haoran Chen's user avatar
2 votes
1 answer
152 views

Clique number of $k$-critical graphs

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$, where $\chi(G)$ denotes the chromatic number of $G$. The ...
CCC's user avatar
  • 41
2 votes
1 answer
173 views

Discrete maximization of geometric mean - reference request

This is a follow-up to my previous MO question: A discrete optimization problem related to the AM-GM inequality Let $n,k$ be integers such that $1\le k\le n$. Define the quantity $$ P(n,k):=\max\ a_1\...
Abdelmalek Abdesselam's user avatar
2 votes
1 answer
130 views

Turán density of hypergraphs with very few edges

As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
domotorp's user avatar
  • 18.5k
4 votes
1 answer
105 views

Are there decompositions of $K_{16}$ by certain 3-regular graphs?

This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering: Can the (edges ...
Wolfgang's user avatar
  • 13.3k
1 vote
2 answers
132 views

Regarding a specific Turán number of graphs

I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have. Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...
vidyarthi's user avatar
  • 2,079
4 votes
0 answers
227 views

Weight transfer proof of Turán’s theorem

Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...
Martin Leshko's user avatar
1 vote
1 answer
118 views

Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$

I know that it must be a simple consequence of the Kővári–Sós–Turán (and Erdős–Stone) theorem, but I am struggling to formulate a proof: Let $H$ be a fixed-size $r$-chromatic graph. Then there exists $...
Yevgeny Levanzov's user avatar
0 votes
2 answers
305 views

Reference for a topological result

I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
Johnny Cage's user avatar
  • 1,543
5 votes
1 answer
104 views

Maximal graphs with a property that is invariant w.r.t. vertex removal

Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$. Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
Max Alekseyev's user avatar
5 votes
1 answer
191 views

Cover a graph with small size complete graphs

Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...
walydna's user avatar
  • 53
0 votes
0 answers
53 views

Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$. Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector. Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$. We ...
User8976's user avatar
  • 199
2 votes
1 answer
244 views

Union closed family of sets with at most a certain number of couples of sets with non-empty intersection

Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most: $$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \...
Fabius Wiesner's user avatar
3 votes
0 answers
92 views

Harper's theorem on the general Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is $$ \min_{S\subseteq ...
Or Meir's user avatar
  • 419
3 votes
0 answers
249 views

Behrend's construction vs. Triangle removal lemma

I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand. Theorem 2.3.1 (Triangle removal lemma) For all $\...
RFZ's user avatar
  • 320
6 votes
1 answer
199 views

Graphs without short cycles and with linear number of edges

Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...
Victor's user avatar
  • 655
4 votes
1 answer
458 views

Turán's theorem for cosets of groups

Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
Veronica Phan's user avatar
10 votes
0 answers
185 views

Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
abacaba's user avatar
  • 364
1 vote
0 answers
70 views

Graph removal lemma

The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...
X. Li's user avatar
  • 373
2 votes
0 answers
53 views

A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side. For sets $X \subseteq U$ and $Y \subseteq V$, let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
Or Meir's user avatar
  • 419
4 votes
1 answer
190 views

Quasi-random vs pseudo-random graphs

My question is somehow concerning terminology on extremal graph theory. Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
Johnny Cage's user avatar
  • 1,543
4 votes
1 answer
126 views

On the number of disjoint subsets of a large set families

Let $[n] := \{1,\dots,n\}$, for some large integer $n$, and let $\mathcal{F}$ be a family of 2-element subsets of $[n]$. The famous Erdös-Ko-Rado (EKR) theorem says that if $|\mathcal{F}| > {n - 1 ...
John Hans's user avatar
4 votes
1 answer
174 views

Is there any study on the bounds on the number of even cycles for planar bipartite graphs?

In 1979, Hakimi and Schmeichel [1] initiated such a study by determining the maximum number of triangles and 4-cycles possible in an $n$-vertex planar graph (see also [2] for a small correction). [1] ...
L.C. Zhang's user avatar
  • 1,749
0 votes
0 answers
138 views

Szemeredi's regularity lemma for countably infinite graphs?

Consider the following version of Szemeredi's regularity lemma found in the Fox and Lovasz paper, "A tight lower bound for Szemeredi's regularity lemma", arXiv: 1403.1768v1 [math.CO] 7 Mar ...
Thomas Benjamin's user avatar
10 votes
1 answer
343 views

Dense triangle-free graphs and their independent sets

Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...
Zach Hunter's user avatar
  • 3,413
6 votes
5 answers
533 views

Existence of connected set with large edge boundary

Let $\Gamma=(V,E)$ be a finite connected graph. Pretty standard notation. Given a set $S\subset V$, write $\Gamma|_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\...
H A Helfgott's user avatar
  • 19.3k
6 votes
1 answer
452 views

Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
4 votes
2 answers
264 views

Intuition on inequality in proving a bound on the sum of squares of degrees of a graph

Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality $$\...
AspiringMat's user avatar
4 votes
1 answer
319 views

The upper bound of edges of the generalized cactus graphs

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple ...
L.C. Zhang's user avatar
  • 1,749
5 votes
0 answers
140 views

$K_4$ or n vertices without triangles

For which minimal $m(n)$ any graph on $m$ vertices contains either a complete subgraph on 4 vertices $K_4$ or $n$-vertices subgraph without triangles? I know a quadratic upper bound $2n^2$, but I am ...
Alexei Fedotov's user avatar

1
2 3 4 5