All Questions
Tagged with extremal-graph-theory co.combinatorics
61 questions with no upvoted or accepted answers
13
votes
0
answers
741
views
Is there a weak strong regularity lemma?
A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
- 29k
11
votes
0
answers
195
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 ...
- 384
10
votes
0
answers
176
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 ...
- 5,590
10
votes
0
answers
222
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
- 986
9
votes
0
answers
156
views
Minimal number of colours in distinguishing colouring of biconnected graphs
A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...
- 4,535
9
votes
0
answers
442
views
An extremal problem for graphs having every edge contained in a 4-clique
This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...
- 2,966
7
votes
0
answers
152
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(...
- 71
7
votes
0
answers
177
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 ...
- 50.8k
6
votes
0
answers
76
views
Cage graphs and even cycles
Let $G$ be a $(\nu,g)$-cage graph of degree $\nu$ with girth $g$ and $n=n(\nu,g)$ vertices.
Based on the known examples, I am wondering if the following can be proved/disproved:
Is it true that ...
- 13.4k
6
votes
0
answers
315
views
Algorithms for computing the Resilience of Graphs
The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
- 903
6
votes
0
answers
889
views
Cliques of hyperedges
Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...
- 1,288
5
votes
0
answers
156
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 ...
- 115
4
votes
0
answers
113
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., ...
- 557
4
votes
0
answers
241
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, ...
4
votes
0
answers
257
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 ...
- 3,612
4
votes
0
answers
104
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 ...
- 3,446
4
votes
0
answers
116
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
- 211
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
- 13.2k
4
votes
0
answers
125
views
Percolation in torus under threshold rule
As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two ...
- 41
4
votes
0
answers
46
views
Two possible generalizations of a theorem of Kotlov about the Hamming Cube
The following theorem is proved here
Let $Q_n=(V,E)$ be the Hamming graph, and let $S \subseteq V$, $|S|<2^{n-1}$. Then the induced subgraph on $V \setminus S$, $Q_n[V \setminus S]$, has a ...
- 736
4
votes
0
answers
434
views
Smallest matrix covered by many random n by n matrices
We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
- 51
3
votes
0
answers
331
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 $\...
- 330
3
votes
0
answers
70
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 ...
- 20.2k
3
votes
0
answers
94
views
The pagenumber of subdivision of a complete graph
A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The book thickness $...
- 767
3
votes
0
answers
66
views
An extremal problem in directed path systems
The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:
What is the asymptotically maximum $L = L(n)$ such that ...
- 1,389
3
votes
0
answers
97
views
What is the number of independent sets in graph of this type?
Suppose we have a graph $G(V,E)$
What is the number of independent sets in graph of this type?
I have an idea to use reccurence
$$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$
where $|G|$ is the ...
2
votes
0
answers
48
views
On planar graphs with specific spanning tree count and poly number of vertices
Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.9k
2
votes
0
answers
61
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$, ...
- 281
2
votes
0
answers
54
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 ...
- 419
2
votes
0
answers
108
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 ...
- 1,190
2
votes
0
answers
99
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 $...
- 20.2k
2
votes
0
answers
78
views
Maximum cardinality general factor of a graph
Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
2
votes
0
answers
301
views
The Turán problem for graphs with given chromatic number
The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r +...
- 462
2
votes
0
answers
285
views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of $...
- 418
2
votes
0
answers
148
views
Smallest size for an incomplete tournament with property $S_k$
By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq ...
- 3,595
1
vote
0
answers
141
views
Specific regularity in bipartite graphs
Let $G(A,B)$ be a bipartite graph with $|A| = |B| = n$, where $n$ is sufficiently large(thus, $o(n)/n,o(n^2)/n^2\ll 1$). The edge density of $G$ is $d = \frac{e(A,B)}{n^2}$, where $e(A,B)$ denotes the ...
- 359
1
vote
0
answers
63
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 359
1
vote
0
answers
107
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 ...
- 19.1k
1
vote
0
answers
74
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 $...
- 373
1
vote
0
answers
79
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 ...
- 135
1
vote
0
answers
123
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 \...
- 5,590
1
vote
0
answers
62
views
Cut norm and biclique gap?
Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...
- 13.9k
1
vote
0
answers
54
views
Constructing graphs from subsets of a minimal alphabet
From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...
- 13.4k
1
vote
1
answer
299
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
- 11
1
vote
0
answers
131
views
What are constructions for induced $C_5$-free graphs?
During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...
- 19.1k
0
votes
0
answers
57
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 359
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 359
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 359
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 359
0
votes
0
answers
68
views
Proving we can minimize the number of crossings by having a planar embedding of $K_{2,2}$ encircle another out of any 2 such embeddings
Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $...
- 1