Search Results

You are looking at 1 - 10 of 13 items for

  • Author: Piotr Rudnicki x
Clear All Modify Search
Open access

Piotr Rudnicki

Dilworth's Decomposition Theorem for Posets

The following theorem is due to Dilworth [8]: Let P be a partially ordered set. If the maximal number of elements in an independent subset (anti-chain) of P is k, then P is the union of k chains (cliques).

In this article we formalize an elegant proof of the above theorem for finite posets by Perles [13]. The result is then used in proving the case of infinite posets following the original proof of Dilworth [8].

A dual of Dilworth's theorem also holds: a poset with maximum clique m is a union of m independent sets. The proof of this dual fact is considerably easier; we follow the proof by Mirsky [11]. Mirsky states also a corollary that a poset of r x s + 1 elements possesses a clique of size r + 1 or an independent set of size s + 1, or both. This corollary is then used to prove the result of Erdős and Szekeres [9].

Instead of using posets, we drop reflexivity and state the facts about anti-symmetric and transitive relations.

Open access

Jessica Enright and Piotr Rudnicki

Helly Property for Subtrees

We prove, following [5, p. 92], that any family of subtrees of a finite tree satisfies the Helly property.

MML identifier: HELLY, version: 7.8.09 4.97.1001

Open access

Piotr Rudnicki and Lorna Stewart


Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for simple graphs as at most 1-dimensional complexes.

We formalize this new setting and then reprove Mycielski’s [12] construction resulting in a triangle-free graph with arbitrarily large chromatic number. A different formalization of similar material is in [15].

Open access

Broderick Arneson and Piotr Rudnicki

Recognizing Chordal Graphs: Lex BFS and MCS1

We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25].

This work is a part of the MSc work of the first author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions.

Open access

Broderick Arneson and Piotr Rudnicki

Chordal Graphs

We are formalizing [9, pp. 81-84] where chordal graphs are defined and their basic characterization is given. This formalization is a part of the M.Sc. work of the first author under supervision of the second author.

Open access

Piotr Rudnicki and Lorna Stewart

The Mycielskian of a Graph

Let ω(G) and χ(G) be the clique number and the chromatic number of a graph G. Mycielski [11] presented a construction that for any n creates a graph Mn which is triangle-free (ω(G) = 2) with χ(G) > n. The starting point is the complete graph of two vertices (K 2). M(n+1) is obtained from Mn through the operation μ(G) called the Mycielskian of a graph G.

We first define the operation μ(G) and then show that ω(μ(G)) = ω(G) and χ(μ(G)) = χ(G) + 1. This is done for arbitrary graph G, see also [10]. Then we define the sequence of graphs Mn each of exponential size in n and give their clique and chromatic numbers.

Open access

Adam St. Arnaud and Piotr Rudnicki


We first provide a modified version of the proof in [3] that the Sorgenfrey line is T 1. Here, we prove that it is in fact T2, a stronger result. Next, we prove that all subspaces of ℝ1 (that is the real line with the usual topology) are Lindel¨of. We utilize this result in the proof that the Sorgenfrey line is Lindel¨of, which is based on the proof found in [8]. Next, we construct the Sorgenfrey plane, as the product topology of the Sorgenfrey line and itself. We prove that the Sorgenfrey plane is not Lindel¨of, and therefore the product space of two Lindel¨of spaces need not be Lindel¨of. Further, we note that the Sorgenfrey line is regular, following from [3]:59. Next, we observe that the Sorgenfrey line is normal since it is both regular and Lindel¨of. Finally, we prove that the Sorgenfrey plane is not normal, and hence the product of two normal spaces need not be normal. The proof that the Sorgenfrey plane is not normal and many of the lemmas leading up to this result are modelled after the proof in [3], that the Niemytzki plane is not normal. Information was also gathered from [15].

Open access

Krystyn Sosada, Ireneusz Mazur and Piotr Rudnicki

Spontaneous Skin Fistula of the Lumbar Area - Case Report

Cutaneous fistulas of the lumbar area are rarely diagnosed. The presented case concerned a 46-year old female patient who underwent surgical treatment in 2008, at the Department of General and Bariatric Surgery, and Emergency Medicine. After twelve months of ineffective conservative therapy of a purulent cutaneous fistula the patient was directed to the Department of Surgery for radical excision of the lesion. After performing additional diagnostic examinations the patient underwent planned surgery, including the complete excision of the fistula canal, which had no contact with the peritoneal cavity. Numerous deposits were observed in the lumen of the fistula. Chemical analysis of the abovementioned demonstrated a 100% content of calcium oxalate, characteristic of urolithiasis. The patient was discharged from the hospital on the eighth day after the operation in good general condition, and with a properly healing wound. Both patient history and examination were unable to definitely determine the cause of the fistula.

Open access

Piotr Rudnicki, Ireneusz Mazur, Konstanty Ślusarczyk, Jerzy Piecuch, Piotr Łopata, Janusz Jopek and Henryk Grzybek

Morphological Changes in the Stomach Mucosa of Rats Caused by Endogenous Bile Acids

"Bile reflux" is a common term to denote a process of placing duodenal contents in the stomach and/or lower oesophagus. It is most often associated with functional or organic failure of the pylorus and is a not uncommon postoperative condition after pyloric section, resection or by-passing.

Gastrotoxicity of the replaced small intestinal mixture leading to lesions in gastric mucosal barrier, is caused by an increased ability to reabsorb hydrogen ions along with migration of blood proteins and electrolytes towards lumen of the stomach. Consequently, histamine secretion becomes increased, leading to inflammatory and haemorrhagic changes or ulcer niches.

The aim of the study was to demonstrate histological and microscopic changes in the gastric mucosa following reflux and to determine if long-term exposure to refluxed duodenal contents will produce tumorous changes in the organs tested.

Material and methods. The study consisted of 25 mature female Wistar rats weighing 180-200 g. Bile reflux to the stomach was produced experimentally by surgical drainage. Final evaluation was performed after 55 weeks.

Results. Findings were as follows: gastric changes were noted in basal and parietal cells, no tumorous foci were found in histological samples. Slight morphological changes can be caused by short periods of gastric mucosa exposure to the gastrotoxic small intestinal mixture.

Conclusions. Endogenous bile acids cause morphological changes in the stomach mucosa of rats. In particular, these changes affect the ultrastructure of basal and parietal cells. No neoplastic foci were found in the examined organs.

Open access

Izabela Polowczyk, Anna Bastrzyk, Tomasz Koźlecki, Piotr Rudnicki, Wojciech Sawiński, Zygmunt Sadowski and Adam Sokołowski

Application of fly ash agglomerates in the sorption of arsenic

The scope of this contribution was to investigate in detail an application of fly ash adsorbent for the removal of arsenite ions from à dilute solution. The experiments have been carried out using fly ash from black coal burning power plant "Siersza" and brown coal burning power plant "Turów" (Poland), which was wetted, then mixed and tumbled in the granulator with a small amount of cement to increase the mechanical strength of agglomerates. The measurements of arsenic adsorption from the aqueous solution were carried out in the flask (with shaking), as well as in the column (with circulation), in order to compare two different methods of contacting waste with adsorbent. The adsorption isotherms of arsenic were determined for granulated material, using the Freundlich model. Kinetics studies indicated that the sorption follows a pseudo-first-order (PFO) model (Lagergren) and the Elovich-type model.