Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Experimental Mathematics Approach to Several Combinatorial Problems
54
0
0.0
(
0
)
Authors
Yukun Yao
Ask ChatGPT about the research
No Arabic abstract
Experimental mathematics is an experimental approach to mathematics in which programming and symbolic computation are used to investigate mathematical objects, identify properties and patterns, discover facts and formulas and even automatically prove theorems. With an experimental mathematics approach, this dissertation deals with several combinatorial problems and demonstrates the methodology of experimental mathematics. We start with parking functions and their moments of certain statistics. Then we discuss about spanning trees and almost diagonal matrices to illustrate the methodology of experimental mathematics. We also apply experimental mathematics to Quicksort algorithms to study the running time. Finally we talk about the interesting peaceable queens problem.
rate research
Read More
The emph{$q,t$-Catalan numbers} $C_n(q,t)$ are polynomials in $q$ and $t$ that reduce to the ordinary Catalan numbers when $q=t=1$. These polynomials have important connections to representation theory, algebraic geometry, and symmetric functions. Haglund and Haiman discovered combinatorial formulas for $C_n(q,t)$ as weighted sums of Dyck paths (or equivalently, integer partitions contained in a staircase shape). This paper undertakes a combinatorial investigation of the joint symmetry property $C_n(q,t)=C_n(t,q)$. We conjecture some structural decompositions of Dyck objects into mutually opposite subcollections that lead to a bijective explanation of joint symmetry in certain cases. A key new idea is the construction of infinite chains of partitions that are independent of $n$ but induce the joint symmetry for all $n$ simultaneously. Using these methods, we prove combinatorially that for $0leq kleq 9$ and all $n$, the terms in $C_n(q,t)$ of total degree $binom{n}{2}-k$ have the required symmetry property.
The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order $n$ can be made isomorphic by changing o(n^2) edges. Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erdos-Simonovits Stability Theorem. Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fraction
To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let $mathcal{G}(g,c,n)$ be the set of graphs $G$ with girth $g(G)=g$, circumference $c(G)=c$, and $n$ vertices; and let $mathcal{H}(g,c,m)$ be the set of graphs with girth $g$, circumference $c$, and $m$ edges. In this work, we study the four following extremal problems on graphs: $A(g,c,n)=min{delta(G),|; G in mathcal{G}(g,c,n) }$, $B(g,c,n)=max{delta(G),|; G in mathcal{G}(g,c,n) }$, $alpha(g,c,m)=min{delta(G),|; in mathcal{H}(g,c,m) }$ and $beta(g,c,m)=max{delta(G),|; G in mathcal{H}(g,c,m) }$. In particular, we obtain bounds for $A(g,c,n)$ and $alpha(g,c,m)$, and we compute the precise value of $B(g,c,n)$ and $beta(g,c,m)$ for all values of $g$, $c$, $n$ and $m$.
We count the numbers of primitive periodic orbits on families of 4-regular directed circulant graphs with $n$ vertices. The relevant counting techniques are then extended to count the numbers of primitive pseudo orbits (sets of distinct primitive periodic orbits) up to length $n$ that lack self-intersections, or that never intersect at more than a single vertex at a time repeated exactly twice for each self-intersection (2-encounters of length zero), for two particular families of graphs. We then regard these two families of graphs as families of quantum graphs and use the counting results to compute the variance of the coefficients of the quantum graphs characteristic polynomial.
We introduce an extension, indexed by a partially ordered set P and cardinal numbers k,l, denoted by (k,l)-->P, of the classical relation (k,n,l)--> r in infinite combinatorics. By definition, (k,n,l)--> r holds, if every map from the n-element subsets of k to the subsets of k with less than l elements has a r-element free set. For example, Kuratowskis Free Set Theorem states that (k,n,l)-->n+1 holds iff k is larger than or equal to the n-th cardinal successor l^{+n} of the infinite cardinal k. By using the (k,l)-->P framework, we present a self-contained proof of the first authors result that (l^{+n},n,l)-->n+2, for each infinite cardinal l and each positive integer n, which solves a problem stated in the 1985 monograph of Erdos, Hajnal, Mate, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation (l^{+(n-1)},r,l)-->2^m, where m is the largest integer below (1/2)(1-2^{-r})^{-n/r}, for every infinite cardinal l and all positive integers n and r with r larger than 1 but smaller than n. For example, (aleph_{210},4,aleph_0)-->32,768. Other order-dimension estimates yield relations such as (aleph_{109},4,aleph_0)--> 257 (using an estimate by Furedi and Kahn) and (aleph_7,4,aleph_0)-->10 (using an exact estimate by Dushnik).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
