许贵桥
|
On the power of standard information for  -approximation in the average case setting
|
We study the equivalence of tractability for classes of  of function evaluations and  of all continuous linear functional for  -approximation in the average-case setting. For the normalized error criterion, we show that the power of is the same as that of for all notions of exponential tractability and algebraic tractability, in the sense that there exist algorithms using function values at some deterministic points which enjoy the same tractability properties as those using optimally chosen linear functional. Moreover, for the absolute error criterion, we also show that the power of is the same as that of for all notions of exponential tractability and algebraic tractability under certain assumptions on the trace of the covariance operators.
|
张彪
|
Chromatic nonsymmetric polynomials of Dyck graphs are slide-positive
|
Motivated by the study of Macdonald polynomials, Haglund and Wilson introduced a nonsymmetric polynomial analogue of the chromatic quasisymmetric function called the chromatic nonsymmetric polynomial of a Dyck graph. We give a positive expansion for this polynomial in the basis of fundamental slide polynomials using recent work of Assaf and Bergeron on flagged $(P,\rho)$-partitions. We then derive the known expansion for the chromatic quasisymmetric function of Dyck graphs in terms of Gessel's fundamental basis by taking a backstable limit of our expansion. This work is joint with Vasu Tewari and Andy Wilson.
|
刘洋
|
Nonsolvable groups with few character codegrees
|
Let G be a finite group and Irr(G) be the the set of irreducible characters of G. The codegree of an irreducible character χ is defined as |G:ker(χ)|/χ(1). In this talk, we will give a classification of nonsolvable groups with four or five character codegrees. This is a join work with Yong Yang.
|
韩苗苗
|
Group Connectivity under $3$-Edge-Connectivity
|
Let $S,T$ be two distinct finite Abelian groups with $|S|=|T|$.A fundamental theorem of Tutte shows that a graph admits a nowhere-zero $S$-flowif and only if it admits a nowhere-zero $T$-flow. Jaeger et al. in 1992 introduced group connectivity as an extension of flow theory, and they asked whether such a relation holds for group connectivity analogy.It was negatively answered by Hu\v{s}ek et al. in 2017 for graphs with edge-connectivity 2for the groups $S=\Z_4$ and $T=\Z_2^2$. In this talk, we extend their resultsto $3$-edge-connected graphs (including both cubic and general graphs),which answers open problems proposed by Hu\v{s}ek et al.(2017) and Lai et al.(2011).Combining some previous results, this characterizes all the equivalence of group connectivity under $3$-edge-connectivity, showing that every$3$-edge-connected $S$-connected graph is $T$-connected if and only if $\{S,T\}\neq\{\Z_4,\Z_2^2\}$
|
冀蒙
|
Hardness results for strong conflict-free connection number of graphs
|
Let $G$ be an(a) edge(vertex)-colored graph. A path $P$ of $G$ is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of $P$.The graph $G$ is called conflict-free (vertex-)connected if any two distinct vertices of $G$ are connected by a conflict-free path, whereas the graph $G$ is calledstrongly conflict-free connected if any two distinct vertices $u,v$ of $G$ are connected by a conflict-free path of length of a shortest path between $u$ and $v$ in $G$.For a connected graph $G$, the (strong) conflict-free connection number of $G$, denoted by $(scfc(G)) \ cfc(G)$, is defined as the smallest number of colors that are required to make $G$(strongly) conflict-free connected.
In this paper, we first investigate the question: Given a connected graph $G$ and a coloring $c: E(or\ V)\rightarrow \{1,2,\cdots,k\} \ (k\geq 1)$ of $G$,determine whether or not $G$ is, respectively, conflict-free connected, conflict-free vertex-connected, strongly conflict-free connected under the coloring $c$.We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether $scfc(G)\leq k$ $(k\geq 2)$ for a given graph $G$is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a $k$-edge-coloring $(k\geq 2)$ of $G$ such that all pairs $(u,v)\in P \ (P\subset V\times V)$ arestrongly conflict-free connected.
|
目的地搜索