All Questions
Tagged with co.combinatorics graph-theory
2,301 questions
0
votes
0
answers
23
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 516
5
votes
3
answers
284
views
The max-clique chromatic number of a graph
Let $G = (V,E)$ be a graph. Every clique, that is, complete subgraph, is
contained in a maximal clique with respect to $\subseteq$ (this is
an easy consequence of Zorn's Lemma). Let $\newcommand{\MC}{\...
- 48.8k
1
vote
0
answers
123
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
0
votes
0
answers
34
views
separator and vertex-connectivity
A definition of "separator" is the following: Let $G$ is an $n$-vertex graph, then $S\subseteq V(G)$ is a separator if there is a partition $V=A\cup B\cup S$ such that $|A|,|B|\le 2n/3$ and ...
- 281
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 24.9k
2
votes
1
answer
111
views
Is there a ternary Cayley graph on 27 vertices that is a non-complete core?
Is there a non-complete ternary Cayley graph that is a core with $3^3 = 27$ vertices?
By a ternary Cayley graph, I mean a (simple, undirected) graph whose vertex set is $\mathbb{Z}_3^n := \bigoplus_{i ...
- 331
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 48.8k
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 1,190
4
votes
0
answers
67
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
0
votes
0
answers
56
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, ...
- 349
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
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 ...
- 349
0
votes
0
answers
36
views
Construct a maximum matching from a minimum vertex cover in bipartite graph?
Konig's theorem in graph theory says that for a bipartite graph $G$, the size of maximum matching in $G$ is equal to the size of minimum vertex cover of $G$.
Typically, one of the proofs is to ...
- 281
1
vote
1
answer
90
views
Characterizing the family of maximal cliques of a cograph
Preamble #1
There are two common equivalent definitions of cographs:
the smallest class that includes $K_1$ and is closed under disjoint union and complementation (or join);
the finite $P_4$-free ...
- 113
2
votes
0
answers
172
views
How many maximal length snakes are there?
This problem was motivated by the classic phone game Snake.
Consider the square grid graph with vertex set $V := \{1, \dots, N\}^2$, for fixed odd positive integer $N$, and an edge between $(x, y)$ ...
- 6,155
4
votes
0
answers
90
views
Definition of Loop in an Oriented Matroid
I had posted this on Stackexchange because I don't believe this is a particlarly difficult question, but there were no answers, so I'm posting it on here now.
I just had a quick question about the ...
- 61
2
votes
2
answers
210
views
Rank of adjacency matrix of a graph on a sphere all of whose faces have four vertices
Let $G$ be a graph drawn on the sphere such that every face of $G$ has exactly four vertices. Question: can anything be said about the rank of the adjacency matrix of $G$ in terms of other (preferably ...
- 2,964
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
0
votes
1
answer
123
views
Petersen graph does not have a nowhere-zero 4-flow
I try to prove that the Petersen graph does not have a nowhere-zero 4-flow (i.e., over $\mathbb{Z}_4$), but I don't know how a proof could work...
I'm happy about every hint, thank you in advance!
2
votes
1
answer
100
views
Clique number and a special partition
Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that ...
- 21
2
votes
1
answer
226
views
Expanders except for commutativity?
What would you call a graph that is an expander except for commutativity, in the following sense?
Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your ...
- 20.2k
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
4
votes
1
answer
371
views
Looking for a counterexample to a strengthening of the union-closed sets conjecture
[Now crossposted at math.stackexchange]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ ...
- 990
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
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 ...
- 349
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 ...
- 349
1
vote
0
answers
72
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 349
1
vote
2
answers
386
views
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 990
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
0
votes
1
answer
71
views
Forced monochromatic pairs in graphs
Starting point. Consider the "$V$-graph" on the vertex set $\{1,2,3\}$ and let the edges be $\{1,2\}$ and $\{2,3\}$. This graph is clearly bipartite. It is a trivial observation that ...
- 48.8k
0
votes
1
answer
82
views
Is there a stiff graph that is not a core?
By a graph, I mean a simple, undirected graph with no loops. A graph homomorphism $f : G \to H$ is a function from the vertexset of $G$ to the vertexset of $H$ such that if $u$ and $v$ are adjacent ...
- 331
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
9
votes
1
answer
216
views
Distinct closed walks with $2n$ steps in the $n$-dimensional hypercube
I am interested in finding out what are the shortest closed walks that touch all $n$ dimensions in an $n$-dimensional hypercube. Because they must be closed and they must touch all $n$ dimensions, the ...
- 323
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
1
vote
0
answers
54
views
Finding a path of given length with maximal relative weight
Let $G$ be a directed graph with vertices $V$ and edges $E \subset V\times V$. A path of length $n \geq 2$ in $G$ is a sequence of vertices $(i_{0},i_{1},\ldots,i_{n-1})$ such that $(i_{k},i_{k+1}) \...
- 798
0
votes
0
answers
120
views
Is there an existing problem related to inferring a hidden node in a graph from its neighbors
My original question was a bit too ambiguous, so I updated it as follows:
Consider a graph $G=(V,E)$. A vertex in $G$ is chosen uniformly at random; then a neighbor $x$ of $v$ is chosen uniformly at ...
- 109
2
votes
0
answers
124
views
Symmetric matching in special graphs
Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part.
Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $...
1
vote
1
answer
59
views
Bounding the number of fully connected vertex subsets of a graph
I have a graph $G$ on $n$ vertices with edge density $p$. I am most interested in $p=O(1)$ but I would also appreciate ideas for the sparse case. My goal is to bound the number of subsets $A,B\...
- 541
2
votes
1
answer
173
views
Connected partitions of bounded degree graphs with parts of bounded sizes
A connected partition of a graph is a partition of its vertex-set such that the induced subgraph on each part is connected.
Question 1: Are there real numbers $c\ge1$ and $r\ge1$ such that for any ...
- 277
0
votes
0
answers
67
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
5
votes
1
answer
409
views
4-color theorem for hypergraphs
Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors?
Below are the definitions to make this precise.
If $H = (V, E)$ is a hypergraph ...
- 48.8k
0
votes
0
answers
63
views
Arrangements of fixed $k$-polyplets in a $n\times n$ matrix
Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
- 47
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
0
votes
1
answer
80
views
Infinite complete minor in $\min,\max$-graph on $\mathbb{N}$
Let $[\omega]^2 =\big\{\{x,y\}:x\neq y \in \omega\big\}$ denote the collection of all 2-element subsets of the non-negative integers. Let $$E=\big\{\{p,q\} : p,q \in [\omega]^2 \text{ and } \max(p)=\...
- 48.8k
-3
votes
1
answer
144
views
Count arrangements with pairs of attacking kings [closed]
I have a $1\times n$ chessboard and $2$ pairs of kings in it. Both components of each pair of kings must be adjacent in the chessboard, that is, they must be attacking.
Now, I want to calculate the ...
- 47
1
vote
0
answers
420
views
Average cluster size of an $n\times n$ matrix
I asked a question about the cluster size inside a vector here. As a result, I finally used the expression $\frac{n}{-k+n+1}$ as the average cluster size, although it´s not proved correct for every ...
- 47
1
vote
1
answer
838
views
Covering a connected bounded-degree bipartite graph with connected subgraphs
Let $G = (L,R,E)$ be a finite connected bipartite graph with maximum degree $\Delta\ge2$. A subgraph $H$ is said to be left-neighbourhood closed (LNC for short) if every $v\in L(H)$ satisfies $\...
- 277
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