Combinatorics (math.CO)

Abstract: The Ramsey's theorem says that a graph with sufficiently many vertices contains a clique or stable set with many vertices. Now we attach some parameter to every vertex, such as degree. Consider the case a graph with sufficiently many vertices of large degree, we can get the realted Ramsey-type result. The Ramsey's theorem of connected version says that every connected graph with sufficiently many vertices contains an induced path, clique or star with many vertices. Now we require the vertex is non-trivial, i.e. the parameter of this vertex is non-trivial, such as $\operatorname{deg}(v)\not =1$. A connected graph with sufficiently many non-trivial vertices must contain some special induced subgraph. We also get the non-connected version of this Ramsey-type result as a corollary.

Abstract: A $q$-graph $H$ on $n$ vertices is a set of vectors of length $n$ with all entries from $\{0,1,\dots,q\}$ and every vector (that we call a $q$-edge) having exactly two non-zero entries. The support of a $q$-edge $\mathbf{x}$ is the pair $S_{\mathbf{x}}$ of indices of non-zero entries. We say that $H$ is an $s$-copy of an ordinary graph $F$ if $|H|=|E(F)|$, $F$ is isomorphic to the graph with edge set $\{S_{\mathbf{x}}:\mathbf{x}\in H\}$, and whenever $v\in e,e'\in E(F)$, the entries with index corresponding to $v$ in the $q$-edges corresponding to $e$ and $e'$ sum up to at least $s$. E.g., the $q$-edges $(1,3,0,0,0), (0,1,0,0,3)$, and $(3,0,0,0,1)$ form a 4-triangle. The Tur\'an number $\mathrm{ex}(n,F,q,s)$ is the maximum number of $q$-edges that a $q$-graph $H$ on $n$ vertices can have if it does not contain any $s$-copies of $F$. In the present paper, we determine the asymptotics of $\mathrm{ex}(n,F,q,q+1)$ for many graphs $F$.

Abstract: A 1-removed subgraph $G_f$ of a graph $G=(V,E)$ is obtained by $(i)$ selecting at most one edge $f(v)$ for each vertex $v\in V$, such that $v\in f(v)\in E$ (the mapping $f:V\to E \cup \{\varnothing\}$ is allowed to be non-injective), and $(ii)$ deleting all the selected edges $f(v)$ from the edge set $E$ of $G$. Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Tur\'an-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as $\omega_1(G)$. This invariant is defined as the minimum chromatic number $\chi(G_f)$ among all 1-removed subgraphs $G_f$ of $G$. We also examine other standard graph invariants in a similar manner.

Abstract: A 1-selection $f$ of a graph $G$ is a function $f: V(G)\rightarrow E(G)$ such that $f(v)$ is incident to $v$ for every vertex $v$. The 1-removed $G_f$ is the graph $(V(G),E(G)\setminus f[V(G)])$. The (1-)robust chromatic number $\chi_1(G)$ is the minimum of $\chi(G_f)$ over all 1-selections $f$ of $G$. We determine the robust chromatic number of complete multipartite graphs and Kneser graphs and prove tight lower and upper bounds on the robust chromatic number of chordal graphs and some of their extensively studied subclasses, with respect to their ordinary chromatic number.

Abstract: An acyclic edge coloring of a graph is a proper edge coloring without any bichromatic cycles. The acyclic chromatic index of a graph $G$ denoted by $a'(G)$, is the minimum $k$ such that $G$ has an acyclic edge coloring with $k$ colors. Fiam\v{c}\'{\i}k conjectured that $a'(G) \le \Delta+2$ for any graph $G$ with maximum degree $\Delta$. A graph $G$ is said to be $k$-degenerate if every subgraph of $G$ has a vertex of degree at most $k$. Basavaraju and Chandran proved that the conjecture is true for $2$-degenerate graphs. We prove that for a $3$-degenerate graph $G$, $a'(G) \le \Delta+5$, thereby bringing the upper bound closer to the conjectured bound. We also consider $k$-degenerate graphs with $k \ge 4$ and give an upper bound for the acyclic chromatic index of the same.

Abstract: An edge $e$ of a graph $G$ is called deletable for some orientation $o$ if the restriction of $o$ to $G-e$ is a strong orientation. In 2021, H\"orsch and Szigeti proposed a new parameter for $3$-edge-connected graphs, called the Frank number, which refines $k$-edge-connectivity. The Frank number is defined as the minimum number of orientations of $G$ for which every edge of $G$ is deletable in at least one of them. They showed that every $3$-edge-connected graph has Frank number at most $7$ and that in case these graphs are also $3$-edge-colourable graphs the parameter is at most $3$. Here we strengthen the latter result by showing that such graphs have Frank number $2$, which also confirms a conjecture by Bar\'at and Bl\'aszik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number $2$ and use them in an algorithm to computationally show that the Petersen graph is the only cyclically $4$-edge-connected cubic graph up to $36$ vertices having Frank number greater than $2$.

Abstract: A graph $G$ is divisible by a graph $H$ if the characteristic polynomial of $G$ is divisible by that of $H$. In this paper, a necessary and sufficient condition for recursive graphs to be divisible by a path is used to show that the H-shape graph $P_{2,2;n-4}^{2,n-7}$, known to be (for $n$ large enough) the minimizer of the spectral radius among the graphs of order $n$ and diameter $n-5$, is determined by its adjacency spectrum if and only if $n \neq 10,13,15$.

Abstract: In this paper we discuss potentially practical ways to produce expander graphs with good spectral properties and a compact description. We focus on several classes of uniform and bipartite expander graphs defined as random Schreier graphs of the general linear group over the finite field of size two. We perform numerical experiments and show that such constructions produce spectral expanders that can be useful for practical applications. To find a theoretical explanation of the observed experimental results, we used the method of moments to prove upper bounds for the expected second largest eigenvalue of the random Schreier graphs used in our constructions. We focus on bounds for which it is difficult to study the asymptotic behaviour but it is possible to compute non-trivial conclusions for relatively small graphs with parameters from our numerical experiments (e.g., with less than 2^200 vertices and degree at least logarithmic in the number of vertices).

Abstract: In this PhD thesis we develop the frame work of triple crossing diagram maps (TCD maps), which describes constrained configurations of points in projective spaces and discrete dynamics on these configurations. We are able to capture the constraints and dynamics of a large list of examples that occur in discrete differential geometry (DDG), discrete integrable systems and exactly solvable models. We explain how to apply various geometric operations to TCD maps, including projections, intersections with hyperplanes and projective dualization. In fact, we show how many examples in the literature are related by the aforementioned operations. Moreover, we introduce a hierarchy of cluster structures on TCD maps, thus answering the open question how objects of DDG relate to cluster structures. At the same time, the general cluster structure reproduces cluster structures known for the pentagram map, T-graphs and t-embeddings. We also explain how the cluster structures behave under geometric operations. Via the cluster structures, the TCD maps are also related to the probabilistic dimer model. The spanning tree model and the Ising model can be obtained as special cases of the dimer model, and we investigate how these special cases relate to geometry. This also leads to two new incidence theorems in relation to quadrics and null-polarities in $\mathbb C \mathrm P^3$. Finally, we also show how TCD maps relate to the Fock-Goncharov moduli spaces of projective flag configurations.

Abstract: Given a lattice path $\nu$, the $\nu$-Tamari lattice and the $\nu$-Dyck lattice are two natural examples of partial order structures on the set of lattice paths that lie weakly above $\nu$. In this paper, we introduce a more general family of lattices, called alt $\nu$-Tamari lattices, which contains these two examples as particular cases. Unexpectedly, we show that all these lattices have the same number of linear intervals.