Markov chains,Gauss soups,and compromise dynamics

It must have been around 1966 when I first met Klaus Krickeberg at a conference in Greece. In my memory it was Konrad Jacobs who encouraged some young people from Erlangen to attend. I still remember when Klaus took us, M. Sieveking, J. Köhn and me, to a quite exciting tour by car on the Peloppenese. Later on, times were exciting too when I was around 1970 assistent to Klaus in Heidelberg. I also remember David G. Kendall at the Greece-conference, telling us about the Delphi method. About this I had forgotten until recently when writing this paper I noticed that my current work on opinion dynamics is related to the Delphi method.     

The automorphism group of a product of hypergraphs

A theorem of G. Sabidussi (1959, Duke Math. J. 26, 693–696) gives necessary and sufficient conditions for the automorphism group of the wreath product of two graphs to be the wreath product of their respective automorphism groups. In this paper we define a wreath product of hypergraphs and prove a theorem extending that of Sabidussi.     

Prime graphs and exponential composition of species

In this paper, we enumerate prime graphs with respect to the Cartesian multiplication of graphs. We use the unique factorization of a connected graph into the product of prime graphs given by Sabidussi to find explicit formulas for labeled and unlabeled prime graphs. In the case of species, we construct the exponential composition of species based on the arithmetic product of species of Maia and Méndez, and express the species of connected graphs as the exponential composition of the species of prime graphs.     

Graphs indecomposable with respect to the X-join

In his paper [3], Sabidussi defined the X-join of a family of graphs. This concept has also appeared in the work of Foulis and Randall on empirical logic [1,2]. In this paper, we investigate those graphs which do not have a nontrivial representation as the X-join of some family of graphs.     

Factoring cartesian-product graphs

In a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge set E(G) of a connected graph G to decompose G into a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,” Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,” European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,” Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from finite to infinite graphs.     

You want them to remember? Then make it memorable! Means for enhancing operations research education

In this article I summarize the main points I made in the keynote presentation of the same title I gave at the EURO XXIV conference in Lisbon, Portugal in July of 2010. Each of these points deals in some way with making communications between an operations research professional (academic or practitioner) and a student, client, subordinate, supervisor, or colleague more effective. Furthermore, each point is directly related to some realization (or epiphany) that I have had with regard to communication since I began teaching ORMS in 1984. It is noteworthy that these communications share a common objective; we are trying to facilitate learning. Since I have spent most of my career in academia, my primary emphasis is on communication with students (particularly those enrolled in introductory ORMS courses). However, I have also spent a great deal of time working on operations research problems outside of academia, either as an employee in private industry or as an operations research consultant to corporations and not-for-profit organizations, and I hope as a consequence my discussion is also relevant to those working in the practice of ORMS.     

Circle graphs and the cycle double cover conjecture

The long standing Cycle Double Cover Conjecture states that every bridgeless graph can be covered by a family of cycles such that every edge is covered exactly twice. Intimately related is the problem of finding, in an eulerian graph, a circuit decomposition compatible with a given transition system (transition systems are also known as decompositions into closed paths). One approach that seems promising consists in finding a black anticlique in the corresponding Sabidussi orbit of bicolored circle graphs.     

A Novel Interpretation of Plato’s Theory of Forms

In several recent issues of this journal, I argued for an account of property possession as strict, numerical identity. While this account has stuck some as being highly idiosyncratic in nature, it is not entirely something new under the sun, since as I will argue in this paper, it turns out to have a historic precedent in Plato’s theory of forms. Indeed, the purpose of this paper is twofold. The first is to show that my account of property possession can be utilized to provide a novel interpretation of Plato’s theory of forms. And the second is to show that once it has been divorced from a variety of implausible doctrines with which it has historically been wedded, Plato’s central insight that all properties possess themselves, far from being of mere historical interest, is independently plausible, ironically enough, even from an empirical point of view.     

Use of stochastic and mathematical programming in?portfolio theory and practice

Standard finance portfolio theory draws graphs and writes equations usually with no constraints and frequently in the univariate case. However, in reality, there are multivariate random variables and multivariate asset weights to determine with constraints. Also there are the effects of transaction costs on asset prices in the theory and calculation of optimal portfolios in the static and dynamic cases. There we use various stochastic programming, linear complementary, quadratic programming and nonlinear programming problems. This paper begins with the simplest problems and builds the theory to the more complex cases and then applies it to real financial asset allocation problems, hedge funds and professional racetrack betting. This paper is based on a keynote lecture at the APMOD conference in Madrid in June 2006. It was also presented at the London Business School. Many thanks are due to APMOD organizers Antonio Alonso-Ayuso, Laureano Escudero, and Andres Ramos for inviting me and for excellent hospitality in Madrid. Thanks are also due to my teachers at Berkeley who got me on the right track on stochastic and mathematical programming, especially Olvi Mangasarian, Roger Wets and Willard Zangwill, and my colleagues and co-authors on portfolio theory in finance and horseracing, especially Chanaka Edirishinge, Donald Hausch, Jarl Kallberg, Victor Lo, Leonard MacLean, Raymond Vickson and Yonggan Zhao.     

Rethinking common belief,revision, and backward induction

Whether rationality and common belief in rationality jointly entail the backward inductive outcome in centipede games has long been debated. Stalnaker’s compelling negative argument appeals to the AGM belief revision postulates to argue that off-path moves may be rational, given the revisions they may prompt. I counter that the structure of common belief and the principles of AGM justify an additional assumption about revision. I then prove that, given my proposed constraint, for all finite, n-player, extensive form, perfect information games with a unique backward inductive solution, if there is initial common belief in rationality, then backward induction is guaranteed.     

图Cn及其r-冠的新的优美标号

研究了关于图的r-冠的优美标号的一个问题,证明了：当n≡0,3（mod 4）时,图Cn及其r-冠是优美图,所给出的新的优美标号不同于现有文献中得到的结果.进而证明了当n≡0（mod 4）时,图Cn及其r-冠也是交错图.     

完全多部图的无符号Laplacian特征多项式(英文)

For a simple graph G,let matrix Q（G）=D（G） + A（G） be it’s signless Laplacian matrix and Q G （λ）=det（λI Q） it’s signless Laplacian characteristic polynomial,where D（G） denotes the diagonal matrix of vertex degrees of G,A（G） denotes its adjacency matrix of G.If all eigenvalues of Q G （λ） are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K（n₁,n₂,···,n_t）.We prove that the complete t-partite graphs K（n,n,···,n）t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K（m,···,m）s（n,···,n）t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K（m,···,m,）s1（n,···,n,）s2（l,···,l）s3.     

A note on the principle of mathematical induction,intuition and consciousness in the light of ideas of Poincaré and Galois

In his argumentation for the non-computability of thought-processes (in general) Penrose is invoking Gödel’s theorem (see [R. Penrose, Shadows of the Mind – A search for the Missing Science of Consciousness, Oxford University Press, Oxford, 1994]). It is the aim with the following note to indicate that the same effect may be obtained in a simpler and possibly also more fundamental way. This does not necessarily mean that I fully believe in Penrose’s thesis – the question is still largely open – but I think that my note indicates that there are a lot of items that remains to be clarified before a satisfactory scientific consensus will be reached. There is a huge gap between the precision of strict scientific contexts and those where this kind of processes are going on. At the same time we will see that the same kind of ideas had been impinging themselves on mathematicians like Poincaré and Galois, like Penrose himself of a very intuitive kind. It is plausible that the solution of the enigma of the scientific character of processes referring back to themselves lies in deep properties of autonomous systems. The self-referential character of the interpretations in Gödel’s theorem is quite central. This will be the subject of a forthcoming paper.     

In Defence of a Minimal Conception of Epistemic Contextualism: A Reply to M. D. Ashfield’s Response

The article responds to the objections M.D. Ashfield has raised to my recent attempt at saving epistemic contextualism from the knowability problem. First, it shows that Ashfield’s criticisms of my minimal conception of epistemic contextualism, even if correct, cannot reinstate the knowability problem. Second, it argues that these criticisms are based on a misunderstanding of the commitments of my minimal conception. I conclude that there is still no reason to maintain that epistemic contextualism has the knowability problem.     

Against the Minimalistic Reading of Epistemic Contextualism: A Reply to Wolfgang Freitag

Several philosophers have argued that the factivity of knowledge poses a problem for epistemic contextualism (EC), which they have construed as a knowability problem. On a proposed minimalistic reading of EC’s commitments, Wolfgang Freitag argues that factivity yields no knowability problem for EC. I begin by explaining how factivity is thought to generate a contradiction out of paradigmatic contextualist cases on a certain reading of EC’s commitments. This reductio results in some kind of reflexivity problem for the contextualist when it comes to knowing her theory: either a knowability problem or a statability problem. Next, I set forth Freitag’s minimalistic reading of EC and explain how it avoids the reductio, the knowability problem and the statability problem. I argue that despite successfully evading these problems, Freitag’s minimalistic reading saddles EC with several other serious problems and should be rejected. I conclude by offering my own resolution to the problems.     

An epistemic model of an agent who does not reflect on reasoning processes

This paper introduces an epistemic model of a boundedly rational agent under the two assumptions that (i) the agent’s reasoning process is in accordance with the model but (ii) the agent does not reflect on these reasoning processes. For such a concept of bounded rationality a semantic interpretation by the possible world semantics of the Kripke (1963) type is no longer available because the definition of knowledge in these possible world semantics implies that the agent knows all valid statements of the model. The key to my alternative semantic approach is the extension of the method of truth tables, first introduced for the propositional logic by Wittgenstein (1922), to an epistemic logic so that I can determine the truth value of epistemic statements for all relevant truth conditions. In my syntactic approach I define an epistemic logic–consisting of the classical calculus of propositional logic plus two knowledge axioms–that does not include the inference rule of necessitation, which claims that an agent knows all theorems of the logic. As my main formal result I derive a determination theorem linking my semantic with my syntactic approach. The difference between my approach and existing knowledge models is illustrated in a game-theoretic application concerning the epistemic justification of iterative solution concepts.     

On external-memory MST, SSSP and multi-way planar graph separation

Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.The results in this paper fall in two main classes. First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs.